[THUWC 2020] Yazid 的棋

Luogu

IDLGP10301

Time8000ms

Memory512MB

DifficultyP7

2020O2优化THUWC

给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或**棋子已移动了 $s$ 步**。对于最终棋子停留的节点，我们把它叫做这次操作的**终点**。做完这些后，Yazid 会将该棋子移出游戏。你需要预测 Yazid 每次操作的终点编号。需要注意的是，所有操作都是有后效性的。也就是说，在前 $Q-1$ 步操作时**消失的边**、**经过的次数**都**不会**在第 $Q$ 次操作时被重置，即下一步操作在上一步操作基础上进行。 ## Input 第一行两个用空格隔开的整数 $n,m$。接下来 $m$ 行描述有向图。这部分中第 $i$ 行（$1\leq i\leq m$）包含三个用空格隔开的整数 $u_i,v_i,w_i$，描述一条 $u_i$ 到 $v_i$ 的经过 $w_i$ 次会被删除的有向边。 * 这里保证 $1\leq u_i,v_i\leq n$，$w_i\leq 10^{18}$。接下来一行一个整数 $Q$。接下来 $Q$ 行依次描述各操作，每行两个用空格隔开的整数 $x,s$，描述一个操作。 * 这里保证 $1\leq x\leq n$，$1\leq s\leq 10^{9}$。 ## Output 输出 $Q$ 行，每行一个整数，依次输出各操作的终点。其中第 $i$ 行输出的是第 $i$ 个操作的终点。 [samples] ## Note **【样例解释 #1】** 第一次操作，棋子的移动步骤如下： 1. 在 $7$ 号节点放置一个棋子。 2. $7$ 号节点编号最小的出边是第 $7$ 条边，棋子通过该边移动到 $5$ 号节点。 3. $5$ 号节点编号最小的出边是第 $5$ 条边，棋子通过该边移动到 $2$ 号节点。 4. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。 5. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。 6. $1$ 号节点编号最小的出边是第 $2$ 条边，棋子通过该边移动到 $2$ 号节点。 7. $2$ 号节点编号最小的出边是第 $3$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $3$ 条边已被经过了 $2$ 次，被从图中删去。 8. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。 9. 棋子停留在 $1$ 号节点，故 $1$ 号节点就是此次操作的终点。第二次操作，棋子的移动步骤如下： 1. 在 $6$ 号节点放置一个棋子。 2. $6$ 号节点编号最小的出边是第 $4$ 条边，棋子通过该边移动到 $3$ 号节点。此时，第 $4$ 条边已被经过了 $1$ 次，被从图中删去。 3. $3$ 号节点编号最小的出边是第 $1$ 条边，棋子通过该边移动到 $1$ 号节点。此时，第 $1$ 条边已被经过了 $1$ 次，被从图中删去。 4. 棋子已移动了 $7$ 步，故停留在 $1$ 号节点，$1$ 号节点是此次操作的终点。第三次操作，棋子的移动步骤如下： 1. 在 $6$ 号节点放置一个棋子。 2. $6$ 号节点已没有出边，故棋子只能停留在 $6$ 号节点，故 $6$ 号节点是此次操作的终点。 **【子任务】** 本题有多个子任务，每个子任务可能包含多个测试点，只有通过了一个子任务中的所有测试点才能得到该子任务的分数。每个子任务的测试点满足一些特殊的限制，具体如下表： |子任务编号|$n \le$|$m \le$|$Q \le$|$s \le$|$w \le$|性质|分值| |----|----|----|----|----|----|----|----| |1|$10^5$|$1.5 \times 10^5$|$5000$|$5000$|$10^{18}$|$0$|8| |2|$10^5$|$1.5 \times 10^5$|$5000$|$10^9$|$5000$|$0$|8| |3|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$1$|8| |4|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$2$|$12$| |5|$10^5$|$n - 1$|$10^5$|$10^9$|$10^{18}$|$3$|13| |6|$10^5$|$n$|$10^5$|$10^9$|$10^{18}$|$4$|15| |7|$10^5$|$n + 50$|$10^5$|$10^9$|$10^{18}$|$5$|8| |8|$10^5$|$1.5 \times 10^5$|$10^5$|$10^9$|$10^{18}$|$0$|28| 对于所有测试点，保证 $1 \leq n\leq 10^5$，$1 \leq m\leq 1.5\times 10^5$，$1 \leq Q \leq 10^5$，$1 \leq s \leq 10^9$，$1 \leq w_i \leq 10^{18}$。 - 性质 0：无特殊性质； - 性质 1：图为随机生成，每条边 $(u, v)$ 出现的概率为 $1 / n^2$； - 性质 2：保证 $w_i = 10^{18}$； - 性质 3：保证图构成了一棵有根树。 - 性质 4：保证图构成了一棵环套树。 - 性质 5：保证前 $n$ 条边构成了一棵环套树。

Samples

Input #1

Output #1

1
1
6

Input #2

见附件中的 2.in。

Output #2

见附件中的 2.ans。

API Response (JSON)

{
  "problem": {
    "name": "[THUWC 2020] Yazid 的棋",
    "description": {
      "content": "给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。 这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或*",
      "description_type": "Markdown"
    },
    "platform": "Luogu",
    "limit": {
      "time_limit": 8000,
      "memory_limit": 524288
    },
    "difficulty": {
      "LuoguStyle": "P7"
    },
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "LGP10301"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "给定一张包含 $n$ 个点、$m$ 条边的有向图，点标号从 $1$ 至 $n$，边标号从 $1$ 至 $m$。\n\n这张图的主人 Yazid 将先后执行 $Q$ 次操作，每个操作的形式为：在一个节点 $x$ 放置一个棋子，并设定一个整数 $s$，同时该棋子不停地沿着**编号最小**的出边移动，其中当第 $i$ 条边被经过 $w_i$ 次后就会立刻从图中被删除。棋子会不停移动直到**无出边可走**或*...",
      "is_translate": false,
      "language": "English"
    }
  ]
}

Full JSON Raw Segments