E - Train Delay Editorial /

Time Limit: 2 sec / Memory Limit: 1024 MB

配点 : 475475 点

問題文

Atcoder 国には 11 から NN の番号がついた NN 個の街と、11 から MM の番号がついた MM 本の電車が走っています。
電車 ii は街 AiA_i を時刻 SiS_i に発車し、街 BiB_i に時刻 TiT_i に到着します。

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

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

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

制約

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 2≤M≤2×1052 \leq M \leq 2\times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i,B_i \leq N
  • Ai≠BiA_i \neq B_i
  • 0≤Si<Ti≤1090 \leq S_i < T_i \leq 10^9
  • 1≤X1≤1091 \leq X_1 \leq 10^9
  • 入力は全て整数

入力

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

NN MM X1X_1
A1A_1 B1B_1 S1S_1 T1T_1
⋮\vdots
AMA_M BMB_M SMS_M TMT_M

出力

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

入力例 1Copy

Copy
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

出力例 1Copy

Copy
0 10 0 0 5

街 11 から 22 へ行く電車 11 の到着が 1515 遅れ、時刻 3535 になりました。
街 22 での電車 11 から 33 への乗り換えのため、電車 33 の発車時刻を 1010 遅らせて、時刻 3535 発 時刻 5050 着とします。
さらに街 33 での電車 33 から 66 への乗り換えのため、電車 66 の発車時刻を 55 遅らせて、時刻 5050 発とします。
他の電車は発車を遅らせることなく、元々乗り換え可能だった電車の間を乗り換えることができるため、(X2,X3,X4,X5,X6)=(0,10,0,0,5)(X_2,X_3,X_4,X_5,X_6)=(0,10,0,0,5) は条件を満たします。
また、条件を満たすもののうち和がこれより小さいものは存在しないため、これが答えとなります。

入力例 2Copy

Copy
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

出力例 2Copy

Copy
100 100 100 100 100 100 100 100

入力例 3Copy

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

出力例 3Copy

Copy
0 0 0

Score : 475475 points

Problem Statement

In the nation of Atcoder, there are NN cities numbered 11 to NN, and MM trains numbered 11 to MM. Train ii departs from city AiA_i at time SiS_i and arrives at city BiB_i at time TiT_i.

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

  • Condition: For all pairs (i,j)(i,j) satisfying 1≤i,j≤M1 \leq i,j \leq M, if Bi=AjB_i=A_j and Ti≤SjT_i \leq S_j, then Ti+Xi≤Sj+XjT_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 ii by XiX_i.

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

Constraints

  • 2≤N≤2×1052 \leq N \leq 2\times 10^5
  • 2≤M≤2×1052 \leq M \leq 2\times 10^5
  • 1≤Ai,Bi≤N1 \leq A_i,B_i \leq N
  • Ai≠BiA_i \neq B_i
  • 0≤Si<Ti≤1090 \leq S_i < T_i \leq 10^9
  • 1≤X1≤1091 \leq X_1 \leq 10^9
  • All input values are integers.

Input

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

NN MM X1X_1
A1A_1 B1B_1 S1S_1 T1T_1
⋮\vdots
AMA_M BMB_M SMS_M TMT_M

Output

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

Sample Input 1Copy

Copy
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 1Copy

Copy
0 10 0 0 5

The arrival of train 11 from city 11 to 22 is delayed by 1515 and becomes time 3535.
To allow transfer from train 11 to 33 in city 22, the departure of train 33 is delayed by 1010, making it depart at time 3535 and arrive at time 5050.
Further, to allow transfer from train 33 to 66 in city 33, the departure of train 66 is delayed by 55, making it depart at time 5050.
Other trains can operate without delay while still allowing transfers between originally transferable trains, so (X2,X3,X4,X5,X6)=(0,10,0,0,5)(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 2Copy

Copy
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 2Copy

Copy
100 100 100 100 100 100 100 100

Sample Input 3Copy

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

Sample Output 3Copy

Copy
0 0 0

2025-04-21 (Mon)
04:38:13 +00:00