#include <iostream>
#include <vector>
#include <array>
#include <queue>
#define ll int
using namespace std;
vector <ll> adj[100000];
priority_queue <array<ll, 3>> pq;
queue <ll> Q;
array <ll, 2> dp[100000][330];
ll n, m, q, a, k, b, f, rt = 200, dist[100000], B[100000], in[100000], visited[100000], ver[100000];
void dfs(ll u) {
visited[u] = q;
dist[u] = in[u] = 0;
for (auto v : adj[u]) {
if (visited[v] != q) dfs(v);
++in[v];
}
}
int main() {
cin.tie(0);
ios::sync_with_stdio(0);
cin >> n >> m >> q;
for (int i=0; i<m; ++i) {
cin >> a >> b;
--a, --b;
adj[b].push_back(a);
}
for (int i=0; i<n; ++i) {
B[i] = visited[i] = ver[i] = -1;
while (!pq.empty()) pq.pop();
pq.push({-1, i, -1});
for (int j=0; j<rt; ++j) {
dp[i][j] = {(ll)-1e9, -1};
}
for (auto u : adj[i]) {
pq.push({dp[u][0][0], u, 0});
}
for (int j=0; j<rt; ++j) {
while (!pq.empty()) {
auto [w, u, x] = pq.top();
pq.pop();
if (x != -1 && x != rt-1 && dp[u][x+1][1] != -1) {
pq.push({dp[u][x+1][0], u, x+1});
}
if (x == -1) {
dp[i][j] = {w+1, u};
break;
}
else if (ver[dp[u][x][1]] != i) {
dp[i][j] = {w+1, dp[u][x][1]};
ver[dp[u][x][1]] = i;
break;
}
}
}
}
while (q--) {
cin >> a >> k;
--a;
for (int i=0; i<k; ++i) {
cin >> b;
--b;
B[b] = q;
}
if (k < rt) {
for (int i=0; i<rt; ++i) {
if (dp[a][i][1] == -1) {
cout << "-1\n";
break;
}
if (B[dp[a][i][1]] != q) {
cout << dp[a][i][0] << '\n';
break;
}
}
}
else {
dfs(a);
Q.push(a);
f = -1;
while (!Q.empty()) {
auto u = Q.front();
Q.pop();
if (B[u] != q) f = max(f, dist[u]);
for (auto v : adj[u]) {
--in[v];
dist[v] = max(dist[v], dist[u]+1);
if (!in[v]) Q.push(v);
}
}
cout << f << '\n';
}
}
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:45:14: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
45 | auto [w, u, x] = pq.top();
| ^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6232 KB |
Output is correct |
2 |
Correct |
2 ms |
6236 KB |
Output is correct |
3 |
Correct |
2 ms |
6236 KB |
Output is correct |
4 |
Correct |
2 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
10332 KB |
Output is correct |
6 |
Correct |
6 ms |
10332 KB |
Output is correct |
7 |
Correct |
4 ms |
10332 KB |
Output is correct |
8 |
Correct |
7 ms |
10544 KB |
Output is correct |
9 |
Correct |
7 ms |
10400 KB |
Output is correct |
10 |
Correct |
10 ms |
10332 KB |
Output is correct |
11 |
Correct |
7 ms |
10332 KB |
Output is correct |
12 |
Correct |
6 ms |
10504 KB |
Output is correct |
13 |
Correct |
9 ms |
10332 KB |
Output is correct |
14 |
Correct |
6 ms |
10532 KB |
Output is correct |
15 |
Correct |
5 ms |
10328 KB |
Output is correct |
16 |
Correct |
6 ms |
10332 KB |
Output is correct |
17 |
Correct |
6 ms |
10536 KB |
Output is correct |
18 |
Correct |
5 ms |
10332 KB |
Output is correct |
19 |
Correct |
6 ms |
10332 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6232 KB |
Output is correct |
2 |
Correct |
2 ms |
6236 KB |
Output is correct |
3 |
Correct |
2 ms |
6236 KB |
Output is correct |
4 |
Correct |
2 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
10332 KB |
Output is correct |
6 |
Correct |
6 ms |
10332 KB |
Output is correct |
7 |
Correct |
4 ms |
10332 KB |
Output is correct |
8 |
Correct |
7 ms |
10544 KB |
Output is correct |
9 |
Correct |
7 ms |
10400 KB |
Output is correct |
10 |
Correct |
10 ms |
10332 KB |
Output is correct |
11 |
Correct |
7 ms |
10332 KB |
Output is correct |
12 |
Correct |
6 ms |
10504 KB |
Output is correct |
13 |
Correct |
9 ms |
10332 KB |
Output is correct |
14 |
Correct |
6 ms |
10532 KB |
Output is correct |
15 |
Correct |
5 ms |
10328 KB |
Output is correct |
16 |
Correct |
6 ms |
10332 KB |
Output is correct |
17 |
Correct |
6 ms |
10536 KB |
Output is correct |
18 |
Correct |
5 ms |
10332 KB |
Output is correct |
19 |
Correct |
6 ms |
10332 KB |
Output is correct |
20 |
Correct |
957 ms |
12020 KB |
Output is correct |
21 |
Correct |
645 ms |
11756 KB |
Output is correct |
22 |
Correct |
1002 ms |
11764 KB |
Output is correct |
23 |
Correct |
457 ms |
12004 KB |
Output is correct |
24 |
Correct |
625 ms |
265632 KB |
Output is correct |
25 |
Correct |
627 ms |
265852 KB |
Output is correct |
26 |
Correct |
689 ms |
265948 KB |
Output is correct |
27 |
Correct |
568 ms |
268828 KB |
Output is correct |
28 |
Correct |
574 ms |
268964 KB |
Output is correct |
29 |
Correct |
577 ms |
270044 KB |
Output is correct |
30 |
Correct |
584 ms |
266192 KB |
Output is correct |
31 |
Correct |
595 ms |
266104 KB |
Output is correct |
32 |
Correct |
586 ms |
266320 KB |
Output is correct |
33 |
Correct |
460 ms |
265876 KB |
Output is correct |
34 |
Correct |
459 ms |
265688 KB |
Output is correct |
35 |
Correct |
458 ms |
265596 KB |
Output is correct |
36 |
Correct |
531 ms |
265704 KB |
Output is correct |
37 |
Correct |
498 ms |
265796 KB |
Output is correct |
38 |
Correct |
511 ms |
265848 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
2 ms |
6232 KB |
Output is correct |
2 |
Correct |
2 ms |
6236 KB |
Output is correct |
3 |
Correct |
2 ms |
6236 KB |
Output is correct |
4 |
Correct |
2 ms |
6232 KB |
Output is correct |
5 |
Correct |
4 ms |
10332 KB |
Output is correct |
6 |
Correct |
6 ms |
10332 KB |
Output is correct |
7 |
Correct |
4 ms |
10332 KB |
Output is correct |
8 |
Correct |
7 ms |
10544 KB |
Output is correct |
9 |
Correct |
7 ms |
10400 KB |
Output is correct |
10 |
Correct |
10 ms |
10332 KB |
Output is correct |
11 |
Correct |
7 ms |
10332 KB |
Output is correct |
12 |
Correct |
6 ms |
10504 KB |
Output is correct |
13 |
Correct |
9 ms |
10332 KB |
Output is correct |
14 |
Correct |
6 ms |
10532 KB |
Output is correct |
15 |
Correct |
5 ms |
10328 KB |
Output is correct |
16 |
Correct |
6 ms |
10332 KB |
Output is correct |
17 |
Correct |
6 ms |
10536 KB |
Output is correct |
18 |
Correct |
5 ms |
10332 KB |
Output is correct |
19 |
Correct |
6 ms |
10332 KB |
Output is correct |
20 |
Correct |
957 ms |
12020 KB |
Output is correct |
21 |
Correct |
645 ms |
11756 KB |
Output is correct |
22 |
Correct |
1002 ms |
11764 KB |
Output is correct |
23 |
Correct |
457 ms |
12004 KB |
Output is correct |
24 |
Correct |
625 ms |
265632 KB |
Output is correct |
25 |
Correct |
627 ms |
265852 KB |
Output is correct |
26 |
Correct |
689 ms |
265948 KB |
Output is correct |
27 |
Correct |
568 ms |
268828 KB |
Output is correct |
28 |
Correct |
574 ms |
268964 KB |
Output is correct |
29 |
Correct |
577 ms |
270044 KB |
Output is correct |
30 |
Correct |
584 ms |
266192 KB |
Output is correct |
31 |
Correct |
595 ms |
266104 KB |
Output is correct |
32 |
Correct |
586 ms |
266320 KB |
Output is correct |
33 |
Correct |
460 ms |
265876 KB |
Output is correct |
34 |
Correct |
459 ms |
265688 KB |
Output is correct |
35 |
Correct |
458 ms |
265596 KB |
Output is correct |
36 |
Correct |
531 ms |
265704 KB |
Output is correct |
37 |
Correct |
498 ms |
265796 KB |
Output is correct |
38 |
Correct |
511 ms |
265848 KB |
Output is correct |
39 |
Correct |
652 ms |
266036 KB |
Output is correct |
40 |
Correct |
657 ms |
265996 KB |
Output is correct |
41 |
Correct |
692 ms |
265652 KB |
Output is correct |
42 |
Correct |
682 ms |
265852 KB |
Output is correct |
43 |
Correct |
643 ms |
268672 KB |
Output is correct |
44 |
Correct |
971 ms |
14432 KB |
Output is correct |
45 |
Correct |
956 ms |
13672 KB |
Output is correct |
46 |
Correct |
1012 ms |
13676 KB |
Output is correct |
47 |
Correct |
973 ms |
13400 KB |
Output is correct |
48 |
Correct |
990 ms |
13280 KB |
Output is correct |
49 |
Correct |
624 ms |
269900 KB |
Output is correct |
50 |
Correct |
581 ms |
268660 KB |
Output is correct |
51 |
Correct |
685 ms |
14408 KB |
Output is correct |
52 |
Correct |
670 ms |
13388 KB |
Output is correct |
53 |
Correct |
559 ms |
269420 KB |
Output is correct |
54 |
Correct |
554 ms |
269380 KB |
Output is correct |
55 |
Correct |
520 ms |
268304 KB |
Output is correct |
56 |
Correct |
519 ms |
268240 KB |
Output is correct |
57 |
Correct |
927 ms |
14344 KB |
Output is correct |
58 |
Correct |
962 ms |
14560 KB |
Output is correct |
59 |
Correct |
914 ms |
13408 KB |
Output is correct |
60 |
Correct |
911 ms |
13656 KB |
Output is correct |
61 |
Correct |
791 ms |
273588 KB |
Output is correct |
62 |
Correct |
670 ms |
268492 KB |
Output is correct |
63 |
Correct |
569 ms |
268528 KB |
Output is correct |
64 |
Correct |
1270 ms |
273508 KB |
Output is correct |
65 |
Correct |
954 ms |
268488 KB |
Output is correct |
66 |
Correct |
738 ms |
268364 KB |
Output is correct |
67 |
Correct |
1066 ms |
273596 KB |
Output is correct |
68 |
Correct |
921 ms |
268440 KB |
Output is correct |
69 |
Correct |
734 ms |
268484 KB |
Output is correct |
70 |
Correct |
581 ms |
272924 KB |
Output is correct |
71 |
Correct |
560 ms |
268648 KB |
Output is correct |
72 |
Correct |
542 ms |
268456 KB |
Output is correct |
73 |
Correct |
648 ms |
273500 KB |
Output is correct |
74 |
Correct |
581 ms |
268456 KB |
Output is correct |
75 |
Correct |
553 ms |
268412 KB |
Output is correct |
76 |
Correct |
629 ms |
270388 KB |
Output is correct |
77 |
Correct |
672 ms |
273460 KB |
Output is correct |
78 |
Correct |
608 ms |
273180 KB |
Output is correct |
79 |
Correct |
667 ms |
14424 KB |
Output is correct |
80 |
Correct |
666 ms |
13676 KB |
Output is correct |
81 |
Correct |
661 ms |
13292 KB |
Output is correct |
82 |
Correct |
605 ms |
270428 KB |
Output is correct |
83 |
Correct |
616 ms |
270020 KB |
Output is correct |
84 |
Correct |
707 ms |
269780 KB |
Output is correct |
85 |
Correct |
652 ms |
269092 KB |
Output is correct |
86 |
Correct |
572 ms |
269736 KB |
Output is correct |
87 |
Correct |
589 ms |
269168 KB |
Output is correct |
88 |
Correct |
932 ms |
14676 KB |
Output is correct |
89 |
Correct |
1002 ms |
14424 KB |
Output is correct |
90 |
Correct |
919 ms |
13832 KB |
Output is correct |
91 |
Correct |
972 ms |
13404 KB |
Output is correct |
92 |
Correct |
957 ms |
13280 KB |
Output is correct |
93 |
Correct |
1002 ms |
13280 KB |
Output is correct |
94 |
Correct |
486 ms |
269816 KB |
Output is correct |
95 |
Correct |
430 ms |
269524 KB |
Output is correct |
96 |
Correct |
486 ms |
268560 KB |
Output is correct |
97 |
Correct |
412 ms |
268448 KB |
Output is correct |
98 |
Correct |
460 ms |
268696 KB |
Output is correct |
99 |
Correct |
391 ms |
268424 KB |
Output is correct |
100 |
Correct |
538 ms |
14552 KB |
Output is correct |
101 |
Correct |
448 ms |
14588 KB |
Output is correct |
102 |
Correct |
524 ms |
13536 KB |
Output is correct |
103 |
Correct |
458 ms |
13520 KB |
Output is correct |
104 |
Correct |
493 ms |
13300 KB |
Output is correct |
105 |
Correct |
449 ms |
13304 KB |
Output is correct |
106 |
Correct |
561 ms |
269788 KB |
Output is correct |
107 |
Correct |
560 ms |
269756 KB |
Output is correct |
108 |
Correct |
604 ms |
268720 KB |
Output is correct |
109 |
Correct |
548 ms |
268736 KB |
Output is correct |
110 |
Correct |
541 ms |
268552 KB |
Output is correct |
111 |
Correct |
521 ms |
268532 KB |
Output is correct |
112 |
Correct |
954 ms |
14716 KB |
Output is correct |
113 |
Correct |
1036 ms |
14584 KB |
Output is correct |
114 |
Correct |
927 ms |
13432 KB |
Output is correct |
115 |
Correct |
961 ms |
13664 KB |
Output is correct |
116 |
Correct |
916 ms |
13272 KB |
Output is correct |
117 |
Correct |
991 ms |
13304 KB |
Output is correct |
118 |
Correct |
613 ms |
268848 KB |
Output is correct |
119 |
Correct |
504 ms |
268252 KB |
Output is correct |
120 |
Correct |
513 ms |
268408 KB |
Output is correct |
121 |
Correct |
579 ms |
268816 KB |
Output is correct |
122 |
Correct |
500 ms |
268264 KB |
Output is correct |
123 |
Correct |
512 ms |
268424 KB |
Output is correct |
124 |
Correct |
564 ms |
268828 KB |
Output is correct |
125 |
Correct |
503 ms |
268356 KB |
Output is correct |
126 |
Correct |
497 ms |
268276 KB |
Output is correct |