#include <bits/stdc++.h>
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize("O3")
#pragma GCC target("sse4,avx2,fma,avx")
#define FOR(i, x, y) for (int i = x; i < y; i++)
using namespace std;
const int L = 111;
vector<int> graph[100001];
vector<pair<int, int>> sqrt_farthest[100001];
int a[100001], dp[100001];
bool bad[100001], in_ret[100001];
inline vector<pair<int, int>> merge(vector<pair<int, int>> X, vector<pair<int, int>> Y) {
vector<pair<int, int>> ret;
int xptr = 0;
for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
while (xptr < X.size() && X[xptr].second >= Y[yptr].second) {
if (!in_ret[X[xptr].first]) ret.push_back({X[xptr].first, X[xptr].second + 1});
in_ret[X[xptr].first] = true;
xptr++;
}
if (!in_ret[Y[yptr].first]) ret.push_back(Y[yptr]);
in_ret[Y[yptr].first] = true;
}
while (xptr < X.size() && ret.size() <= L) {
if (!in_ret[X[xptr].first]) ret.push_back({X[xptr].first, X[xptr].second + 1});
in_ret[X[xptr].first] = true;
xptr++;
}
for (pair<int, int> i : ret) in_ret[i.first] = false;
return ret;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
int n, m, k;
cin >> n >> m >> k;
FOR(i, 0, m) {
int u, v;
cin >> u >> v;
graph[u].push_back(v);
}
FOR(i, 1, n + 1) sqrt_farthest[i] = {{i, 0}};
FOR(i, 1, n + 1) for (int j : graph[i]) sqrt_farthest[j] = merge(sqrt_farthest[i], sqrt_farthest[j]);
while (k--) {
int t, y;
cin >> t >> y;
FOR(i, 0, y) {
cin >> a[i];
bad[a[i]] = true;
}
if (y >= L) {
FOR(i, 1, n + 1) dp[i] = (bad[i] ? INT_MIN : 0);
FOR(i, 1, t + 1) for (int j : graph[i]) dp[j] = max(dp[j], dp[i] + 1);
cout << max(-1, dp[t]) << '\n';
} else {
bool can = false;
for (pair<int, int> i : sqrt_farthest[t]) if (!bad[i.first]) {
can = true;
cout << i.second << '\n';
break;
}
if (!can) cout << "-1\n";
}
FOR(i, 0, y) bad[a[i]] = false;
}
return 0;
}
Compilation message
bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(std::vector<std::pair<int, int> >, std::vector<std::pair<int, int> >)':
bitaro.cpp:18:48: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
~~~~~^~~~~~~~~~
bitaro.cpp:18:67: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int yptr = 0; ret.size() <= L && yptr < Y.size() && xptr < X.size(); yptr++) {
~~~~~^~~~~~~~~~
bitaro.cpp:19:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (xptr < X.size() && X[xptr].second >= Y[yptr].second) {
~~~~~^~~~~~~~~~
bitaro.cpp:27:17: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (xptr < X.size() && ret.size() <= L) {
~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
11 ms |
5632 KB |
Output is correct |
6 |
Correct |
11 ms |
5632 KB |
Output is correct |
7 |
Correct |
12 ms |
5504 KB |
Output is correct |
8 |
Correct |
13 ms |
6144 KB |
Output is correct |
9 |
Correct |
15 ms |
6144 KB |
Output is correct |
10 |
Correct |
13 ms |
6144 KB |
Output is correct |
11 |
Correct |
14 ms |
6120 KB |
Output is correct |
12 |
Correct |
11 ms |
5888 KB |
Output is correct |
13 |
Correct |
13 ms |
6144 KB |
Output is correct |
14 |
Correct |
12 ms |
5760 KB |
Output is correct |
15 |
Correct |
11 ms |
5504 KB |
Output is correct |
16 |
Correct |
12 ms |
5760 KB |
Output is correct |
17 |
Correct |
12 ms |
5888 KB |
Output is correct |
18 |
Correct |
11 ms |
5760 KB |
Output is correct |
19 |
Correct |
12 ms |
5888 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
11 ms |
5632 KB |
Output is correct |
6 |
Correct |
11 ms |
5632 KB |
Output is correct |
7 |
Correct |
12 ms |
5504 KB |
Output is correct |
8 |
Correct |
13 ms |
6144 KB |
Output is correct |
9 |
Correct |
15 ms |
6144 KB |
Output is correct |
10 |
Correct |
13 ms |
6144 KB |
Output is correct |
11 |
Correct |
14 ms |
6120 KB |
Output is correct |
12 |
Correct |
11 ms |
5888 KB |
Output is correct |
13 |
Correct |
13 ms |
6144 KB |
Output is correct |
14 |
Correct |
12 ms |
5760 KB |
Output is correct |
15 |
Correct |
11 ms |
5504 KB |
Output is correct |
16 |
Correct |
12 ms |
5760 KB |
Output is correct |
17 |
Correct |
12 ms |
5888 KB |
Output is correct |
18 |
Correct |
11 ms |
5760 KB |
Output is correct |
19 |
Correct |
12 ms |
5888 KB |
Output is correct |
20 |
Correct |
524 ms |
8440 KB |
Output is correct |
21 |
Correct |
516 ms |
8416 KB |
Output is correct |
22 |
Correct |
542 ms |
8516 KB |
Output is correct |
23 |
Correct |
558 ms |
8568 KB |
Output is correct |
24 |
Correct |
731 ms |
91632 KB |
Output is correct |
25 |
Correct |
701 ms |
92128 KB |
Output is correct |
26 |
Correct |
708 ms |
92152 KB |
Output is correct |
27 |
Correct |
741 ms |
112720 KB |
Output is correct |
28 |
Correct |
752 ms |
112876 KB |
Output is correct |
29 |
Correct |
740 ms |
112864 KB |
Output is correct |
30 |
Correct |
736 ms |
112120 KB |
Output is correct |
31 |
Correct |
728 ms |
115776 KB |
Output is correct |
32 |
Correct |
688 ms |
112232 KB |
Output is correct |
33 |
Correct |
560 ms |
76868 KB |
Output is correct |
34 |
Correct |
546 ms |
70636 KB |
Output is correct |
35 |
Correct |
552 ms |
76536 KB |
Output is correct |
36 |
Correct |
640 ms |
95864 KB |
Output is correct |
37 |
Correct |
629 ms |
92536 KB |
Output is correct |
38 |
Correct |
653 ms |
96128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
4992 KB |
Output is correct |
2 |
Correct |
7 ms |
4992 KB |
Output is correct |
3 |
Correct |
7 ms |
5120 KB |
Output is correct |
4 |
Correct |
7 ms |
4992 KB |
Output is correct |
5 |
Correct |
11 ms |
5632 KB |
Output is correct |
6 |
Correct |
11 ms |
5632 KB |
Output is correct |
7 |
Correct |
12 ms |
5504 KB |
Output is correct |
8 |
Correct |
13 ms |
6144 KB |
Output is correct |
9 |
Correct |
15 ms |
6144 KB |
Output is correct |
10 |
Correct |
13 ms |
6144 KB |
Output is correct |
11 |
Correct |
14 ms |
6120 KB |
Output is correct |
12 |
Correct |
11 ms |
5888 KB |
Output is correct |
13 |
Correct |
13 ms |
6144 KB |
Output is correct |
14 |
Correct |
12 ms |
5760 KB |
Output is correct |
15 |
Correct |
11 ms |
5504 KB |
Output is correct |
16 |
Correct |
12 ms |
5760 KB |
Output is correct |
17 |
Correct |
12 ms |
5888 KB |
Output is correct |
18 |
Correct |
11 ms |
5760 KB |
Output is correct |
19 |
Correct |
12 ms |
5888 KB |
Output is correct |
20 |
Correct |
524 ms |
8440 KB |
Output is correct |
21 |
Correct |
516 ms |
8416 KB |
Output is correct |
22 |
Correct |
542 ms |
8516 KB |
Output is correct |
23 |
Correct |
558 ms |
8568 KB |
Output is correct |
24 |
Correct |
731 ms |
91632 KB |
Output is correct |
25 |
Correct |
701 ms |
92128 KB |
Output is correct |
26 |
Correct |
708 ms |
92152 KB |
Output is correct |
27 |
Correct |
741 ms |
112720 KB |
Output is correct |
28 |
Correct |
752 ms |
112876 KB |
Output is correct |
29 |
Correct |
740 ms |
112864 KB |
Output is correct |
30 |
Correct |
736 ms |
112120 KB |
Output is correct |
31 |
Correct |
728 ms |
115776 KB |
Output is correct |
32 |
Correct |
688 ms |
112232 KB |
Output is correct |
33 |
Correct |
560 ms |
76868 KB |
Output is correct |
34 |
Correct |
546 ms |
70636 KB |
Output is correct |
35 |
Correct |
552 ms |
76536 KB |
Output is correct |
36 |
Correct |
640 ms |
95864 KB |
Output is correct |
37 |
Correct |
629 ms |
92536 KB |
Output is correct |
38 |
Correct |
653 ms |
96128 KB |
Output is correct |
39 |
Correct |
712 ms |
90540 KB |
Output is correct |
40 |
Correct |
683 ms |
90360 KB |
Output is correct |
41 |
Correct |
891 ms |
91256 KB |
Output is correct |
42 |
Correct |
827 ms |
90872 KB |
Output is correct |
43 |
Correct |
681 ms |
90360 KB |
Output is correct |
44 |
Correct |
558 ms |
8056 KB |
Output is correct |
45 |
Correct |
536 ms |
7800 KB |
Output is correct |
46 |
Correct |
599 ms |
7928 KB |
Output is correct |
47 |
Correct |
575 ms |
7672 KB |
Output is correct |
48 |
Correct |
521 ms |
7728 KB |
Output is correct |
49 |
Correct |
743 ms |
111608 KB |
Output is correct |
50 |
Correct |
886 ms |
111004 KB |
Output is correct |
51 |
Correct |
549 ms |
7860 KB |
Output is correct |
52 |
Correct |
589 ms |
7420 KB |
Output is correct |
53 |
Correct |
690 ms |
94336 KB |
Output is correct |
54 |
Correct |
679 ms |
90836 KB |
Output is correct |
55 |
Correct |
854 ms |
94200 KB |
Output is correct |
56 |
Correct |
833 ms |
91512 KB |
Output is correct |
57 |
Correct |
571 ms |
7860 KB |
Output is correct |
58 |
Correct |
558 ms |
7852 KB |
Output is correct |
59 |
Correct |
599 ms |
7544 KB |
Output is correct |
60 |
Correct |
599 ms |
7484 KB |
Output is correct |
61 |
Correct |
845 ms |
110936 KB |
Output is correct |
62 |
Correct |
773 ms |
94712 KB |
Output is correct |
63 |
Correct |
747 ms |
90744 KB |
Output is correct |
64 |
Correct |
1103 ms |
110968 KB |
Output is correct |
65 |
Correct |
1040 ms |
94336 KB |
Output is correct |
66 |
Correct |
1022 ms |
91000 KB |
Output is correct |
67 |
Correct |
1357 ms |
111188 KB |
Output is correct |
68 |
Correct |
1290 ms |
94584 KB |
Output is correct |
69 |
Correct |
1294 ms |
90260 KB |
Output is correct |
70 |
Correct |
732 ms |
111048 KB |
Output is correct |
71 |
Correct |
668 ms |
94584 KB |
Output is correct |
72 |
Correct |
651 ms |
90872 KB |
Output is correct |
73 |
Correct |
745 ms |
110840 KB |
Output is correct |
74 |
Correct |
685 ms |
94476 KB |
Output is correct |
75 |
Correct |
675 ms |
91244 KB |
Output is correct |
76 |
Correct |
755 ms |
111468 KB |
Output is correct |
77 |
Correct |
1284 ms |
110968 KB |
Output is correct |
78 |
Correct |
719 ms |
110944 KB |
Output is correct |
79 |
Correct |
556 ms |
7672 KB |
Output is correct |
80 |
Correct |
754 ms |
7288 KB |
Output is correct |
81 |
Correct |
545 ms |
7260 KB |
Output is correct |
82 |
Correct |
730 ms |
110332 KB |
Output is correct |
83 |
Correct |
768 ms |
112120 KB |
Output is correct |
84 |
Correct |
1309 ms |
110292 KB |
Output is correct |
85 |
Correct |
1311 ms |
113132 KB |
Output is correct |
86 |
Correct |
713 ms |
110196 KB |
Output is correct |
87 |
Correct |
744 ms |
112328 KB |
Output is correct |
88 |
Correct |
565 ms |
7672 KB |
Output is correct |
89 |
Correct |
550 ms |
7672 KB |
Output is correct |
90 |
Correct |
745 ms |
7244 KB |
Output is correct |
91 |
Correct |
759 ms |
7160 KB |
Output is correct |
92 |
Correct |
534 ms |
7288 KB |
Output is correct |
93 |
Correct |
528 ms |
7288 KB |
Output is correct |
94 |
Correct |
605 ms |
75236 KB |
Output is correct |
95 |
Correct |
566 ms |
69112 KB |
Output is correct |
96 |
Correct |
1139 ms |
74876 KB |
Output is correct |
97 |
Correct |
1080 ms |
70008 KB |
Output is correct |
98 |
Correct |
583 ms |
75384 KB |
Output is correct |
99 |
Correct |
547 ms |
69624 KB |
Output is correct |
100 |
Correct |
571 ms |
7672 KB |
Output is correct |
101 |
Correct |
557 ms |
7644 KB |
Output is correct |
102 |
Correct |
726 ms |
7288 KB |
Output is correct |
103 |
Correct |
725 ms |
7160 KB |
Output is correct |
104 |
Correct |
547 ms |
7288 KB |
Output is correct |
105 |
Correct |
530 ms |
7260 KB |
Output is correct |
106 |
Correct |
683 ms |
94200 KB |
Output is correct |
107 |
Correct |
692 ms |
91176 KB |
Output is correct |
108 |
Correct |
1218 ms |
94672 KB |
Output is correct |
109 |
Correct |
1221 ms |
90188 KB |
Output is correct |
110 |
Correct |
675 ms |
94764 KB |
Output is correct |
111 |
Correct |
634 ms |
90744 KB |
Output is correct |
112 |
Correct |
558 ms |
7672 KB |
Output is correct |
113 |
Correct |
557 ms |
7672 KB |
Output is correct |
114 |
Correct |
747 ms |
7288 KB |
Output is correct |
115 |
Correct |
768 ms |
7288 KB |
Output is correct |
116 |
Correct |
526 ms |
7160 KB |
Output is correct |
117 |
Correct |
566 ms |
7288 KB |
Output is correct |
118 |
Correct |
735 ms |
110456 KB |
Output is correct |
119 |
Correct |
649 ms |
93944 KB |
Output is correct |
120 |
Correct |
643 ms |
90360 KB |
Output is correct |
121 |
Correct |
719 ms |
110720 KB |
Output is correct |
122 |
Correct |
670 ms |
93944 KB |
Output is correct |
123 |
Correct |
656 ms |
90232 KB |
Output is correct |
124 |
Correct |
707 ms |
110328 KB |
Output is correct |
125 |
Correct |
629 ms |
94248 KB |
Output is correct |
126 |
Correct |
644 ms |
90232 KB |
Output is correct |