E - Train Delay Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475 点

問題文

Atcoder 国には 1 から N の番号がついた N 個の街と、1 から M の番号がついた M 本の電車が走っています。
電車 i は街 A_i を時刻 S_i に発車し、街 B_i に時刻 T_i に到着します。

正の整数 X_1 が与えられるので、0 以上の整数 X_2,\ldots,X_M を以下の条件を満たすように定める方法のうち、X_2+\ldots+X_M が最小になるものを求めてください。

  • 条件：1 \leq i,j \leq M を満たす全ての組 (i,j) について、「B_i=A_j かつ T_i \leq S_j」ならば「T_i+X_i \leq S_j+X_j」
    • すなわち、もともと乗り換え可能だった電車の組は、各電車 i の発車時刻・到着時刻を X_i 遅らせても乗り換え可能である

なお、X_2+\ldots+X_M が最小になるような X_2,\ldots,X_M の定め方は一意であることが証明できます。

制約

  • 2 \leq N \leq 2\times 10^5
  • 2 \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 0 \leq S_i < T_i \leq 10^9
  • 1 \leq X_1 \leq 10^9
  • 入力は全て整数

入力

入力は以下の形式で標準入力から与えられる。

N M X_1
A_1 B_1 S_1 T_1
\vdots
A_M B_M S_M T_M

出力

条件を満たし、和を最小化するような X_2,\ldots,X_M を、この順に空白区切りで出力せよ。

入力例 1

3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

出力例 1

0 10 0 0 5

街 1 から 2 へ行く電車 1 の到着が 15 遅れ、時刻 35 になりました。
街 2 での電車 1 から 3 への乗り換えのため、電車 3 の発車時刻を 10 遅らせて、時刻 35 発 時刻 50 着とします。
さらに街 3 での電車 3 から 6 への乗り換えのため、電車 6 の発車時刻を 5 遅らせて、時刻 50 発とします。
他の電車は発車を遅らせることなく、元々乗り換え可能だった電車の間を乗り換えることができるため、(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) は条件を満たします。
また、条件を満たすもののうち和がこれより小さいものは存在しないため、これが答えとなります。

入力例 2

10 9 100
1 10 0 1
10 2 1 100
10 3 1 100
10 4 1 100
10 5 1 100
10 6 1 100
10 7 1 100
10 8 1 100
10 9 1 100

出力例 2

100 100 100 100 100 100 100 100

入力例 3

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

出力例 3

0 0 0

Score : 475 points

Problem Statement

In the nation of Atcoder, there are N cities numbered 1 to N, and M trains numbered 1 to M. Train i departs from city A_i at time S_i and arrives at city B_i at time T_i.

Given a positive integer X_1, find a way to set non-negative integers X_2,\ldots,X_M that satisfies the following condition with the minimum possible value of X_2+\ldots+X_M.

  • Condition: For all pairs (i,j) satisfying 1 \leq i,j \leq M, if B_i=A_j and T_i \leq S_j, then T_i+X_i \leq S_j+X_j.
    • In other words, for any pair of trains that are originally possible to transfer between, it is still possible to transfer even after delaying the departure and arrival times of each train i by X_i.

It can be proved that such a way to set X_2,\ldots,X_M with the minimum possible value of X_2+\ldots+X_M is unique.

Constraints

  • 2 \leq N \leq 2\times 10^5
  • 2 \leq M \leq 2\times 10^5
  • 1 \leq A_i,B_i \leq N
  • A_i \neq B_i
  • 0 \leq S_i < T_i \leq 10^9
  • 1 \leq X_1 \leq 10^9
  • All input values are integers.

Input

The input is given from Standard Input in the following format:

N M X_1
A_1 B_1 S_1 T_1
\vdots
A_M B_M S_M T_M

Output

Print X_2,\ldots,X_M that satisfy the condition with the minimum possible sum, in that order, separated by spaces.

Sample Input 1

3 6 15
1 2 10 20
1 2 20 30
2 3 25 40
2 3 35 50
3 1 15 30
3 1 45 60

Sample Output 1

0 10 0 0 5

The arrival of train 1 from city 1 to 2 is delayed by 15 and becomes time 35.
To allow transfer from train 1 to 3 in city 2, the departure of train 3 is delayed by 10, making it depart at time 35 and arrive at time 50.
Further, to allow transfer from train 3 to 6 in city 3, the departure of train 6 is delayed by 5, making it depart at time 50.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so (X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) satisfies the condition.
Moreover, there is no solution with a smaller sum that satisfies the condition, so this is the answer.

Sample Input 2

10 9 100
1 10 0 1
10 2 1 100
10 3 1 100
10 4 1 100
10 5 1 100
10 6 1 100
10 7 1 100
10 8 1 100
10 9 1 100

Sample Output 2

100 100 100 100 100 100 100 100

Sample Input 3

4 4 10
1 2 0 1
1 2 0 10
2 3 100 200
2 4 100 200

Sample Output 3

0 0 0