TouchStone
  请登录后使用
登录 注册
 系统首页  练习题库  考试列表  判题结果  问题讨论与解答  统计信息与排名
  • 首页
  • 题库
  • P1599
  • 题目
  • P1599【Usaco Jan07 Silver】最大身高
    限制 : 时间限制 : 10000 MS   空间限制 : 265536 KB
    问题描述

    FJ的N(1 <= N <= 5,000)头奶牛站成一排,并从左到右被编号为1..N。每头奶牛都有一个正整数的身高,具体的值FJ暂时保密,但会告诉你它们当中最高的一头的编号I和身高H(1 <= H <= 1,000,000)的值。

    FJ制作一张包含R(0 <= R <= 10,000)行的列表,每行的都是形如“第17号奶牛能看到第34号奶牛”,其意义是34号奶牛的身高不低于17号奶牛的身高,并且在17号和34号之间的奶牛的身高都严格低于17号奶牛的身高。

    请你确定奶牛每头奶牛的最大可能的身高,我们保证给出的数据都是正确的,并且一定有满足限制条件的解。

    输入格式

    第1行:包含四个用空格分开的整数:N, I, H 和 R
    第2..R+1行:每行包含两个用空格分开的整数A和B(1 <= A,B <= N),表示奶牛A能看到奶牛B

    输出格式

    第1..N行:第i行包含一个整数,表示第i头奶牛的最大身高。

    样例输入

    9 3 5 5
    1 3
    5 3
    4 3
    3 7
    9 8

    样例输出

    5
    4
    5
    3
    4
    4
    5
    5
    5


    来源  Usaco Jan07 Silver