P6145 [USACO20FEB] Timeline G

Bessie has done $N$ milkings over the past $M$ days, but she has forgotten on which day each milking happened. For the $i$-th milking, Bessie remembers that it happened no earlier than day $S_i$. Also, she has $C$ memories, each given as a triple $(a,b,x)$, meaning that the $b$-th milking happened at least $x$ days after the $a$-th milking finished. Now please help Bessie compute the earliest possible day for each milking while satisfying all conditions. It is guaranteed that Bessie's memories are correct, which means there exists at least one valid schedule such that: - The $i$-th milking happens no earlier than day $S_i$ and no later than day $M$. - All memories are satisfied.

The first line contains three integers $N, M, C$. It is guaranteed that $1 \leq N, C \leq 10^5$ and $2 \leq M \leq 10^9$. The next line contains $N$ integers $S_1, S_2, \ldots, S_n$. It is guaranteed that for all $1 \leq i \leq n$, we have $1 \leq S_i \leq M$. The next $C$ lines each contain three integers $a, b, x$, describing one memory. It is guaranteed that $a \neq b$ and $1 \leq x \leq M$.

Output $N$ lines, each containing one integer. The number on line $i$ is the earliest possible day of the $i$-th milking.

- Test cases $2 \sim 4$ satisfy $N, C \leq 10^3$. - Test cases $5 \sim 10$ have no special constraints. Translated by ChatGPT 5