#P11664. [JOI 2025 Final] 缆车 / Mi Teleférico

    ID: 13043 远端评测题 2000ms 1024MiB 尝试: 0 已通过: 0 难度: 5 上传者: 标签>并查集树状数组2025生成树扫描线JOI(日本)

[JOI 2025 Final] 缆车 / Mi Teleférico

题目背景

译自 第24回日本情報オリンピック 本選 T3。

Mi Teleférico 指的是连接玻利维亚拉巴斯市(La Paz)及埃尔阿尔托市(El Alto)的缆车系统。

题目描述

给定一张 NN 个点 MM 条边的有向无环图。这张有向图的边是由 PP 个公司(编号 1P1\sim P)修建的,每条边恰好被一个公司修建。

节点标号 1N1\sim N,第 ii1iM1\le i\le M)条边由节点 AiA_i 指向节点 BiB_i,且是公司 CiC_i 修建的。这里,保证 Ai<BiA_i\lt B_i

QQ 个询问,每个询问给定区间 [L,R][L,R]1LRP1\le L\le R\le P)和钱数 XX。目标是从 11 号点只经过编号 [L,R]\in [L,R] 的公司修建的边,可以到达其他任意一个节点。

为此,可以选择一个新的区间 [l,r][l',r']1lrP1\le l'\le r'\le P),将 [L,R][L,R] 变为 [l,r][l',r']。这会花费 Ll+Rr|L'-l'|+|R-r'| 的代价,这个操作至多只能执行一次。操作的代价必须不大于钱数 XX

对于每个询问,判断是否能够达成目标。

输入格式

如下所示:

NN MM PP
A1A_1 B1B_1 C1C_1
A2A_2 B2B_2 C2C_2
\vdots
AMA_M BMB_M CMC_M
QQ
L1L_1 R1R_1 X1X_1
L2L_2 R2R_2 X2X_2
\vdots
LQL_Q RQR_Q XQX_Q

输出格式

对于第 ii 个询问,如果可以达成,输出一行一个 Yes\texttt{Yes};否则输出一行一个 No\texttt{No}

4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
4
3 7 0
5 6 0
3 4 0
1 9 0
Yes
No
No
Yes
4 6 10
1 2 3
2 4 7
1 2 6
2 3 5
3 4 2
3 4 8
3
5 6 10
3 4 1
7 8 3
Yes
No
Yes
3 1 1000000000
1 2 6
1
1 1000000000 1000000000
No
5 9 2000
2 3 1814
2 3 457
1 2 1226
3 4 1354
1 5 1050
1 2 1725
2 3 1383
1 5 1626
1 4 1795
5
850 1872 128
82 428 1217
487 924 573
1639 1926 202
202 420 25
Yes
Yes
Yes
Yes
No

提示

样例解释

样例 11 解释

11 个询问中,[3,7][3,7] 已经可以满足条件,无需进行操作。

22 个询问中,[5,6][5,6] 不满足条件,然后无法进行任何操作,所以无法达成目标。

该样例满足所有子任务的限制。

样例 22 解释

11 个询问中,选择 l=1,r=5l'=1,r'=5,花费 55 的代价可以达成目标。

该样例满足子任务 2,3,572,3,5\sim 7 的限制。

样例 33 解释

该样例满足子任务 6,76,7 的限制。

样例 44 解释

该样例满足子任务 575\sim 7 的限制。

数据范围

  • 2N3×1052\le N\le 3\times 10^5
  • 1M3×1051\le M\le 3\times 10^5
  • 1P1091\le P\le 10^9
  • 1Ai<BiN1\le A_i\lt B_i\le N1iM1\le i\le M)。
  • 1CiP1\le C_i\le P1iM1\le i\le M)。
  • 1Q4×1051\le Q\le 4\times 10^5
  • 1LiRiP1\le L_i\le R_i\le P1iQ1\le i\le Q)。
  • 0Xi1090\le X_i\le 10^91iQ1\le i\le Q)。
  • 输入的都是整数。

子任务

  1. (7pts)N,M,Q50N,M,Q\le 50Xi=0X_i=01iQ1\le i\le Q)。
  2. (8pts)P10P\le 10
  3. (11pts)P100P\le 100
  4. (23pts)P3×105P\le 3\times 10^5Xi=0X_i=01iQ1\le i\le Q)。
  5. (9pts)P3×105P\le 3\times 10^5
  6. (22pts)N,M8,000N,M\le 8,000
  7. (20pts)无额外限制。