P10199 [Hubei NOI Qualifier Mock 2024] Time and Wind / wind

The wind brings the seeds of stories, and time turns them into myths.

You are flying among $N$ anchor points along $M$ directed air routes using the Wings of Wind. The anchor points are numbered $1,2,\cdots,N$, and the directed routes are numbered $1,2,\cdots,M$. For route $i$, the starting anchor point is $u_i$, and the destination anchor point is $v_i$. Due to Barbatos's mysterious connection with time, route $i$ opens at time $O_i$ and closes **after** time $C_i$. **That is, for any $O_i \le t \le C_i$, you can enter route $i$ from anchor point $u_i$ at time $t$.** After entering a route, spatially you will arrive directly at anchor point $v_i$. Temporally, the time will change **with equal probability** to a real-valued moment corresponding to some real number in $[L_i,R_i]$. **Note that after arriving at an anchor point, you must immediately enter the next route at the same moment; otherwise, you must end the flight there.** You will start from anchor point $S$ and try to visit anchor point $i\ (1\le i\le N)$. You need to determine a path $E_1,E_2,E_3,\cdots,E_k$, where $E_x\ (1\le x\le k)$ denotes a route. The path must satisfy that $E_1$ starts from anchor point $S$, $E_k$ arrives at anchor point $i$, and for $1\le j

The input consists of $M+1$ lines. The first line contains three integers $N,M,S$, representing the number of anchor points, the number of routes, and the starting anchor point. The next $M$ lines each contain six integers $u_i,v_i,O_i,C_i,L_i,R_i$, describing route $i$. The meanings of the variables are given in the description.

Output one line with one integer, representing the maximum value among $T_i$.

### Sample Explanation 1 For anchor point $1$, clearly $T_1=0$. For anchor point $2$, along the path $1 \rightarrow 2$, $T_2=16065$. For anchor point $3$, along the path $1 \rightarrow 2 \rightarrow 3$, $T_3=26795$. For anchor point $4$, along the path $1 \rightarrow 4$, $T_4 = 10131$. Therefore, the answer is $\max T_i=T_3=26795$. ### Subtasks For all testdata, it is guaranteed that $1 \le N,M \le 5\times 10^5$, $1 \le O_i,L_i \le 20$, $1 \le O_i \le C_i \le 10^9$, $1 \le L_i \le R_i \le 10^9$, and $1\le S \le N$. | Test Point ID | $N\le$ | $M\le$ | $C_i,R_i\le$ | Special Property | |:--:|:--:|:--:|:--:|:--:| | $1\sim 4$ | $20$ | $20$ | $10^9$ | None | | $5\sim 8$ | $10^5$ | $10^3$ | $10^9$ | None | | $9\sim 10$ | $5\times 10^5$ | $5\times 10^5$ | $10^9$ | A | | $11\sim 12$ | $10^5$ | $10^5$ | $20$ | None | | $13\sim 14$ | $5\times 10^5$ | $5\times 10^5$ | $10^3$ | None | | $15\sim 20$ | $5\times 10^5$ | $5\times 10^5$ | $10^9$ | None | Special Property A: The number of routes connected to a single anchor point does not exceed $100$. Translated by ChatGPT 5