856 . 貓咪國旅遊計劃

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

abcabcabc

User's AC Ratio

100.0% (2/2)

Submission's AC Ratio

50.0% (4/8)

Tags

ioicamp ioicamp-2025

Description

貓咪國是一個人與貓和平相處的國度，人類養活貓咪，貓咪治癒人類，真是烏托邦一般的世界。最近喜歡貓咪的小桃認識了這樣一個國度，希望能夠接受貓咪們的治癒，決定要到這裡旅遊。

貓咪國有 $N$ 個城市，主要藉由有完善系統的「喵喵車」來讓人們在兩個城市之間移動。更詳細來說，一共有 $M$ 種喵喵車在城市間移動，第 $i$ 種可以將人們從第 $u_i$ 個城市載到第 $v_i$ 個城市，或是從第 $v_i$ 個城市載到第 $u_i$ 個城市。為了從中獲利，貓咪國一共發行了 $10^ 9$ 種車票，編號為 $1, 2, \ldots, 10^ 9$，人們需要出示編號為 $w_i$ 的車票才能搭乘第 $i$ 種喵喵車，但搭乘完後車票不會回收，可以被繼續使用。

另外，每個城市都會設有換票所。第 $i$ 個城市的換票所裡有 $k_i$ 種車票，編號分別為 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, k_i}$。在換票所裡，我們可以挑選任兩種換票所裡有的車票編號 $x, y$，並用一張編號 $x$ 的車票交換一張編號 $y$ 的車票。

了解貓咪國的喵喵車系統後，小桃擬定了 $Q$ 個計劃，第 $i$ 個計劃為她先購買了一張編號為 $l_i$ 的車票，並打算從第 $s_i$ 個城市移動到第 $t_i$ 個城市。對於每個計劃，請幫小桃判斷能不能在不多買任何一張票的情況下抵達城市 $t_i$。

Input Format

輸入第一行有三個正整數 $N, M, Q$，分別代表貓咪國城市的數量、喵喵車的數量以及計劃的數量。

接下來 $M$ 行每行有三個正整數 $u_i, v_i, w_i$，代表第 $i$ 種喵喵車連接的兩個城市與所需的車票種類。

接下來 $N$ 行，每行第一個數字為非負整數 $k_i$，代表第 $i$ 個城市換票所有的車票數量，後面接著 $k_i$ 個相異正整數 $a_{i, 1}, a_{i, 2}, \ldots, a_{i, k_i}$ 代表第 $i$ 個城市的換票所裡有的車票編號。

接下來 $Q$ 行，每行有三個正整數 $s_i, t_i, l_i$，代表第 $i$ 個計劃的起始城市、目標城市與一開始的車票種類。

  • $2 \leq N \leq 10^ 5$
  • $1 \leq M \leq 2 \times 10^ 5$
  • $1 \leq Q \leq 2 \times 10^ 5$
  • $0 \leq k_i$
  • $0 \leq \sum_{i = 1}^ {N} k_i \leq 2 \times 10^ 5$
  • $1 \leq u_i, v_i \leq N, u_i \neq v_i$
  • $1 \leq s_i, t_i \leq N$
  • $1 \leq w_i, l_i, a_{i, j} \leq 10^ 9$
  • $\forall j \neq j', a_{i, j} \neq a_{i, j'}$

Output Format

請輸出 $Q$ 行，若第 $i$ 個計劃能夠達成，請在第 $i$ 行輸出 Yes，否則輸出 No。

Sample Input 1

3 2 5
1 2 1
2 3 2
0
2 1 2
0
1 3 1
1 3 2
3 1 1
3 1 2
2 2 1

Sample Output 1

Yes
No
No
Yes
Yes

Sample Input 2

8 10 5
6 8 1
1 2 1
8 6 1
3 7 1
6 4 1
4 8 1
6 8 1
8 6 1
2 1 1
5 7 1
0
0
0
0
0
0
0
0
4 6 1
2 1 1
7 8 1
2 7 1
7 3 1

Sample Output 2

Yes
Yes
No
No
Yes

Sample Input 3

10 15 8
4 5 2
1 6 2
10 7 2
8 10 2
10 4 1
8 3 4
7 2 3
7 4 2
6 10 1
2 8 3
9 3 4
6 5 3
5 9 4
4 8 2
8 7 3
0
0
0
0
0
0
0
0
0
0
1 6 2
8 6 2
3 9 4
2 8 3
5 3 4
8 3 2
9 3 4
7 10 2

Sample Output 3

Yes
No
Yes
Yes
Yes
No
Yes
Yes

Sample Input 4

5 6 5
1 2 123456789
1 3 987654321
1 4 864197532
2 5 998244353
3 5 777777777
4 5 888888888
2 123456789 987654321
2 123456789 998244353
9 8 6 4 1 9 7 5 3 2
1 48763
0
5 3 998244353
3 4 777777777
2 5 123456789
4 2 48763
1 1 56562

Sample Output 4

Yes
No
Yes
No
Yes

Hints

在範例測試資料一的第一個計劃中，小桃可以用以下流程來抵達第 $3$ 個城市：

  • 搭乘第 $1$ 種喵喵車從第 $1$ 個城市移動到第 $2$ 個城市。
  • 在第 $2$ 個城市的換票所將編號 $1$ 的車票換成編號 $2$。
  • 搭乘第 $2$ 種喵喵車從第 $2$ 個城市移動到第 $3$ 個城市。

Problem Source

Subtasks

No. Testdata Range Constraints Score
1 0~3 範例測資 0
2 1, 4~12 $w_i = l_i = 1, k_i = 0$ 5
3 0~2, 4~30 $w_i, l_i \leq 10$ 15
4 1~2, 4~12, 31~50 $k_i = 0$ 25
5 0~80 無額外限制 55

Testdata and Limits

No. Time Limit (ms) Memory Limit (VSS, KiB) Output Limit (KiB) Subtasks
0 3000 524288 65536 1 3 5
1 3000 524288 65536 1 2 3 4 5
2 3000 524288 65536 1 3 4 5
3 3000 524288 65536 1 5
4 3000 524288 65536 2 3 4 5
5 3000 524288 65536 2 3 4 5
6 3000 524288 65536 2 3 4 5
7 3000 524288 65536 2 3 4 5
8 3000 524288 65536 2 3 4 5
9 3000 524288 65536 2 3 4 5
10 3000 524288 65536 2 3 4 5
11 3000 524288 65536 2 3 4 5
12 3000 524288 65536 2 3 4 5
13 3000 524288 65536 3 5
14 3000 524288 65536 3 5
15 3000 524288 65536 3 5
16 3000 524288 65536 3 5
17 3000 524288 65536 3 5
18 3000 524288 65536 3 5
19 3000 524288 65536 3 5
20 3000 524288 65536 3 5
21 3000 524288 65536 3 5
22 3000 524288 65536 3 5
23 3000 524288 65536 3 5
24 3000 524288 65536 3 5
25 3000 524288 65536 3 5
26 3000 524288 65536 3 5
27 3000 524288 65536 3 5
28 3000 524288 65536 3 5
29 3000 524288 65536 3 5
30 3000 524288 65536 3 5
31 3000 524288 65536 4 5
32 3000 524288 65536 4 5
33 3000 524288 65536 4 5
34 3000 524288 65536 4 5
35 3000 524288 65536 4 5
36 3000 524288 65536 4 5
37 3000 524288 65536 4 5
38 3000 524288 65536 4 5
39 3000 524288 65536 4 5
40 3000 524288 65536 4 5
41 3000 524288 65536 4 5
42 3000 524288 65536 4 5
43 3000 524288 65536 4 5
44 3000 524288 65536 4 5
45 3000 524288 65536 4 5
46 3000 524288 65536 4 5
47 3000 524288 65536 4 5
48 3000 524288 65536 4 5
49 3000 524288 65536 4 5
50 3000 524288 65536 4 5
51 3000 524288 65536 5
52 3000 524288 65536 5
53 3000 524288 65536 5
54 3000 524288 65536 5
55 3000 524288 65536 5
56 3000 524288 65536 5
57 3000 524288 65536 5
58 3000 524288 65536 5
59 3000 524288 65536 5
60 3000 524288 65536 5
61 3000 524288 65536 5
62 3000 524288 65536 5
63 3000 524288 65536 5
64 3000 524288 65536 5
65 3000 524288 65536 5
66 3000 524288 65536 5
67 3000 524288 65536 5
68 3000 524288 65536 5
69 3000 524288 65536 5
70 3000 524288 65536 5
71 3000 524288 65536 5
72 3000 524288 65536 5
73 3000 524288 65536 5
74 3000 524288 65536 5
75 3000 524288 65536 5
76 3000 524288 65536 5
77 3000 524288 65536 5
78 3000 524288 65536 5
79 3000 524288 65536 5
80 3000 524288 65536 5
Submit
Back to Top