Greedy Takahashi

AtCoder

IDabc212_f

Time4000ms

Memory256MB

Difficulty—

There are $N$ cities numbered $1$ through $N$, and $M$ buses that go between these cities. The $i$\-th bus $(1 \leq i \leq M)$ departs from City $A_i$ at time $S_i+0.5$ and arrive at City $B_i$ at time $T_i+0.5$. Takahashi will travel between these $N$ cities. When he is in City $p$ at time $t$, he will do the following. 1. If there is a bus that departs from City $p$ not earlier than time $t$, take the bus that departs the earliest among those buses to get to another city. 2. If there is no such bus, do nothing and stay in City $p$. Takahashi repeats doing the above until there is no bus to take. It is guaranteed that all $M$ buses depart at different times, so the bus to take is always uniquely determined. Additionally, the time needed to change buses is negligible. Here is your task: process $Q$ queries, the $i$\-th $(1 \leq i \leq Q)$ of which is as follows. * If Takahashi begins his travel in City $Y_i$ at time $X_i$, in which city or on which bus will he be at time $Z_i$? ## Constraints * $2 \leq N \leq 10^5$ * $1 \leq M \leq 10^5$ * $1 \leq Q \leq 10^5$ * $1 \leq A_i,B_i \leq N\ (1 \leq i \leq M)$ * $A_i \neq B_i\ (1 \leq i \leq M)$ * $1 \leq S_i \lt T_i \leq 10^9\ (1 \leq i \leq M)$ * $S_i \neq S_j\ (i \neq j)$ * $1 \leq X_i \lt Z_i \leq 10^9\ (1 \leq i \leq Q)$ * $1 \leq Y_i \leq N\ (1 \leq i \leq Q)$ * All values in input are integers. ## Input Input is given from Standard Input in the following format: $N$ $M$ $Q$ $A_1$ $B_1$ $S_1$ $T_1$ $A_2$ $B_2$ $S_2$ $T_2$ $\hspace{1.8cm}\vdots$ $A_M$ $B_M$ $S_M$ $T_M$ $X_1$ $Y_1$ $Z_1$ $X_2$ $Y_2$ $Z_2$ $\hspace{1.2cm}\vdots$ $X_Q$ $Y_Q$ $Z_Q$ [samples]

Samples

Input #1

Output #1

2 3
2
3

In the first query, Takahashi will travel as follows.

1.  Start in City $1$ at time $1$.
2.  Take the bus that departs from City $1$ at time $1.5$ and arrives at City $2$ at time $3.5$.
3.  Take the bus that departs from City $2$ at time $3.5$ and arrives at City $3$ at time $5.5$.
4.  Since no bus departs from City $3$ at time $5.5$ or later, stay in City $3$ (forever).

At time $5$, he will be on the bus that departs from City $2$ and arrives at City $3$. Thus, as specified in the Output section, we should print $2$ and $3$ with a space between them.

Input #2

8 10 10
4 3 329982133 872113932
6 8 101082040 756263297
4 7 515073851 793074419
8 7 899017043 941751547
5 7 295510441 597348810
7 2 688716395 890599546
6 1 414221915 748470452
6 4 810915860 904512496
3 1 497469654 973509612
4 1 307142272 872178157
374358788 4 509276232
243448834 6 585993193
156350864 4 682491610
131643541 8 836902943
152874385 6 495945159
382276121 1 481368090
552433623 2 884584430
580376205 2 639442239
108790644 7 879874292
883275610 1 994982498

Output #2

API Response (JSON)

{
  "problem": {
    "name": "Greedy Takahashi",
    "description": {
      "content": "There are $N$ cities numbered $1$ through $N$, and $M$ buses that go between these cities. The $i$\\-th bus $(1 \\leq i \\leq M)$ departs from City $A_i$ at time $S_i+0.5$ and arrive at City $B_i$ at tim",
      "description_type": "Markdown"
    },
    "platform": "AtCoder",
    "limit": {
      "time_limit": 4000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "abc212_f"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "There are $N$ cities numbered $1$ through $N$, and $M$ buses that go between these cities. The $i$\\-th bus $(1 \\leq i \\leq M)$ departs from City $A_i$ at time $S_i+0.5$ and arrive at City $B_i$ at tim...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments