856 . 貓咪國旅遊計劃

Submit
Status
Discussion / Solution
Ranklist
Back to Problems List

TopCoder

餘切
owoovo is 8

User's AC Ratio

100.0% (15/15)

Submission's AC Ratio

82.8% (24/29)

Tags

ioicamp ioicamp-2025

Description

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

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

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

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

Input Format

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

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

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

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

  • 2≤N≤105
  • 1≤M≤2×105
  • 1≤Q≤2×105
  • 0≤ki
  • 0≤∑i=1Nki≤2×105
  • 1≤ui,vi≤N,ui≠vi
  • 1≤si,ti≤N
  • 1≤wi,li,ai,j≤109
  • ∀j≠j′,ai,j≠ai,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 wi=li=1,ki=0 5
3 0~2, 4~30 wi,li≤10 15
4 1~2, 4~12, 31~50 ki=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