Train Delay

AtCoder

IDabc368_e

Time2000ms

Memory256MB

Difficulty—

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$ [samples]

Samples

Input #1

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.

Input #2

Output #2

100 100 100 100 100 100 100 100

Input #3

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

Output #3

0 0 0

API Response (JSON)

{
  "problem": {
    "name": "Train Delay",
    "description": {
      "content": "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",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc368_e"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "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$.\nGiven a...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments