P2879 [USACO07JAN] Tallest Cow S
题目描述
FJ 的 $N$ 头奶牛($1 \le N \le 10,000$)按编号 $1$ 到 $N$ 排成一行。每头奶牛有一个正整数表示的身高(这是个秘密)。现在你只知道最高奶牛的身高 $H$($1 \le H \le 1,000,000$),以及它的编号 $I$。
FJ 提供了 $R$ 条信息($0 \le R \le 10,000$),每条信息形如“奶牛 17 能看到奶牛 34”。这意味着奶牛 34 的身高不小于奶牛 17 的身高,并且编号在 17 和 34 之间的所有奶牛,其身高都严格小于奶牛 17 的身高。
现在请你计算出对于每一头奶牛(编号从 $1$ 到 $N$),在所有给定信息都成立的前提下,它可能具有的最大身高。
题目保证一定存在满足条件的解。
输入格式
无
输出格式
无