#include<bits/stdc++.h>
using namespace std;
#define rep(a, b) for(int a = 0; a < (b); ++a)
#define st first
#define nd second
#define pb push_back
#define all(a) a.begin(), a.end()
const int LIM=1e5+7, K=100, INF=1e9+7;
vector<int>V[LIM];
vector<pair<int,int>>P[LIM];
int odw[LIM], kiedy[LIM], czy[LIM], najd[LIM], akt, akt2;
void lacz(int a, int b) {
++akt;
vector<pair<int,int>>tmp;
int la=0, lb=0;
while(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
if(kiedy[P[a][la].st]<akt) {
kiedy[P[a][la].st]=akt;
tmp.pb(P[a][la]);
}
++la;
} else {
if(kiedy[P[b][lb].st]<akt) {
kiedy[P[b][lb].st]=akt;
tmp.pb({P[b][lb].st, P[b][lb].nd+1});
}
++lb;
}
}
P[a]=tmp;
}
void DFS(int x) {
odw[x]=1;
P[x].pb({x, 0});
for(auto i : V[x]) {
if(!odw[i]) DFS(i);
lacz(x, i);
}
}
int main() {
ios_base::sync_with_stdio(0); cin.tie(0);
int n, m, q;
cin >> n >> m >> q;
while(m--) {
int a, b;
cin >> a >> b; --a; --b;
V[b].pb(a);
}
rep(i, n) if(!odw[i]) DFS(i);
while(q--) {
int x, y;
cin >> x >> y; --x;
++akt2;
rep(i, y) {
int a;
cin >> a; --a;
czy[a]=akt2;
}
if(y<K) {
int ans=-1;
for(auto i : P[x]) if(czy[i.st]<akt2) ans=max(ans, i.nd);
cout << ans << '\n';
continue;
}
rep(i, x+1) {
if(czy[i]==akt2) najd[i]=-INF;
else najd[i]=0;
for(auto j : V[i]) najd[i]=max(najd[i], najd[j]+1);
}
cout << max(najd[x], -1) << '\n';
}
}
Compilation message
bitaro.cpp: In function 'void lacz(int, int)':
bitaro.cpp:16:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | while(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
| ~~^~~~~~~~~~~~
bitaro.cpp:16:61: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
16 | while(tmp.size()<K && (la<P[a].size() || lb<P[b].size())) {
| ~~^~~~~~~~~~~~
bitaro.cpp:17:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
| ~~^~~~~~~~~~~~~
bitaro.cpp:17:43: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
17 | if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
| ~~^~~~~~~~~~~~
bitaro.cpp:17:56: warning: suggest parentheses around '&&' within '||' [-Wparentheses]
17 | if(lb==P[b].size() || la<P[a].size() && P[a][la].nd>=P[b][lb].nd+1) {
| ~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
5332 KB |
Output is correct |
6 |
Correct |
4 ms |
5332 KB |
Output is correct |
7 |
Correct |
3 ms |
5332 KB |
Output is correct |
8 |
Correct |
4 ms |
5792 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
4 ms |
5716 KB |
Output is correct |
11 |
Correct |
4 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
4 ms |
5716 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
4 ms |
5332 KB |
Output is correct |
16 |
Correct |
4 ms |
5460 KB |
Output is correct |
17 |
Correct |
4 ms |
5588 KB |
Output is correct |
18 |
Correct |
4 ms |
5460 KB |
Output is correct |
19 |
Correct |
4 ms |
5588 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
5332 KB |
Output is correct |
6 |
Correct |
4 ms |
5332 KB |
Output is correct |
7 |
Correct |
3 ms |
5332 KB |
Output is correct |
8 |
Correct |
4 ms |
5792 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
4 ms |
5716 KB |
Output is correct |
11 |
Correct |
4 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
4 ms |
5716 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
4 ms |
5332 KB |
Output is correct |
16 |
Correct |
4 ms |
5460 KB |
Output is correct |
17 |
Correct |
4 ms |
5588 KB |
Output is correct |
18 |
Correct |
4 ms |
5460 KB |
Output is correct |
19 |
Correct |
4 ms |
5588 KB |
Output is correct |
20 |
Correct |
148 ms |
6840 KB |
Output is correct |
21 |
Correct |
141 ms |
6916 KB |
Output is correct |
22 |
Correct |
152 ms |
7016 KB |
Output is correct |
23 |
Correct |
141 ms |
6944 KB |
Output is correct |
24 |
Correct |
287 ms |
69432 KB |
Output is correct |
25 |
Correct |
288 ms |
70572 KB |
Output is correct |
26 |
Correct |
273 ms |
70224 KB |
Output is correct |
27 |
Correct |
297 ms |
89000 KB |
Output is correct |
28 |
Correct |
256 ms |
89036 KB |
Output is correct |
29 |
Correct |
258 ms |
88832 KB |
Output is correct |
30 |
Correct |
272 ms |
88932 KB |
Output is correct |
31 |
Correct |
268 ms |
87372 KB |
Output is correct |
32 |
Correct |
250 ms |
88652 KB |
Output is correct |
33 |
Correct |
247 ms |
59372 KB |
Output is correct |
34 |
Correct |
205 ms |
53528 KB |
Output is correct |
35 |
Correct |
235 ms |
58864 KB |
Output is correct |
36 |
Correct |
256 ms |
74312 KB |
Output is correct |
37 |
Correct |
241 ms |
70348 KB |
Output is correct |
38 |
Correct |
242 ms |
74028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4948 KB |
Output is correct |
2 |
Correct |
3 ms |
4948 KB |
Output is correct |
3 |
Correct |
2 ms |
4948 KB |
Output is correct |
4 |
Correct |
2 ms |
4948 KB |
Output is correct |
5 |
Correct |
4 ms |
5332 KB |
Output is correct |
6 |
Correct |
4 ms |
5332 KB |
Output is correct |
7 |
Correct |
3 ms |
5332 KB |
Output is correct |
8 |
Correct |
4 ms |
5792 KB |
Output is correct |
9 |
Correct |
4 ms |
5716 KB |
Output is correct |
10 |
Correct |
4 ms |
5716 KB |
Output is correct |
11 |
Correct |
4 ms |
5716 KB |
Output is correct |
12 |
Correct |
6 ms |
5588 KB |
Output is correct |
13 |
Correct |
4 ms |
5716 KB |
Output is correct |
14 |
Correct |
4 ms |
5460 KB |
Output is correct |
15 |
Correct |
4 ms |
5332 KB |
Output is correct |
16 |
Correct |
4 ms |
5460 KB |
Output is correct |
17 |
Correct |
4 ms |
5588 KB |
Output is correct |
18 |
Correct |
4 ms |
5460 KB |
Output is correct |
19 |
Correct |
4 ms |
5588 KB |
Output is correct |
20 |
Correct |
148 ms |
6840 KB |
Output is correct |
21 |
Correct |
141 ms |
6916 KB |
Output is correct |
22 |
Correct |
152 ms |
7016 KB |
Output is correct |
23 |
Correct |
141 ms |
6944 KB |
Output is correct |
24 |
Correct |
287 ms |
69432 KB |
Output is correct |
25 |
Correct |
288 ms |
70572 KB |
Output is correct |
26 |
Correct |
273 ms |
70224 KB |
Output is correct |
27 |
Correct |
297 ms |
89000 KB |
Output is correct |
28 |
Correct |
256 ms |
89036 KB |
Output is correct |
29 |
Correct |
258 ms |
88832 KB |
Output is correct |
30 |
Correct |
272 ms |
88932 KB |
Output is correct |
31 |
Correct |
268 ms |
87372 KB |
Output is correct |
32 |
Correct |
250 ms |
88652 KB |
Output is correct |
33 |
Correct |
247 ms |
59372 KB |
Output is correct |
34 |
Correct |
205 ms |
53528 KB |
Output is correct |
35 |
Correct |
235 ms |
58864 KB |
Output is correct |
36 |
Correct |
256 ms |
74312 KB |
Output is correct |
37 |
Correct |
241 ms |
70348 KB |
Output is correct |
38 |
Correct |
242 ms |
74028 KB |
Output is correct |
39 |
Correct |
352 ms |
69744 KB |
Output is correct |
40 |
Correct |
293 ms |
70012 KB |
Output is correct |
41 |
Correct |
519 ms |
70512 KB |
Output is correct |
42 |
Correct |
334 ms |
70456 KB |
Output is correct |
43 |
Correct |
297 ms |
69964 KB |
Output is correct |
44 |
Correct |
222 ms |
7324 KB |
Output is correct |
45 |
Correct |
153 ms |
6896 KB |
Output is correct |
46 |
Correct |
223 ms |
7080 KB |
Output is correct |
47 |
Correct |
159 ms |
6836 KB |
Output is correct |
48 |
Correct |
169 ms |
6900 KB |
Output is correct |
49 |
Correct |
346 ms |
89136 KB |
Output is correct |
50 |
Correct |
466 ms |
88824 KB |
Output is correct |
51 |
Correct |
178 ms |
7244 KB |
Output is correct |
52 |
Correct |
192 ms |
6900 KB |
Output is correct |
53 |
Correct |
302 ms |
73860 KB |
Output is correct |
54 |
Correct |
312 ms |
70252 KB |
Output is correct |
55 |
Correct |
479 ms |
73888 KB |
Output is correct |
56 |
Correct |
496 ms |
70628 KB |
Output is correct |
57 |
Correct |
175 ms |
7300 KB |
Output is correct |
58 |
Correct |
189 ms |
7276 KB |
Output is correct |
59 |
Correct |
210 ms |
6840 KB |
Output is correct |
60 |
Correct |
195 ms |
6936 KB |
Output is correct |
61 |
Correct |
296 ms |
88768 KB |
Output is correct |
62 |
Correct |
283 ms |
74072 KB |
Output is correct |
63 |
Correct |
303 ms |
69916 KB |
Output is correct |
64 |
Correct |
381 ms |
88816 KB |
Output is correct |
65 |
Correct |
415 ms |
73936 KB |
Output is correct |
66 |
Correct |
377 ms |
70496 KB |
Output is correct |
67 |
Correct |
459 ms |
88756 KB |
Output is correct |
68 |
Correct |
467 ms |
74164 KB |
Output is correct |
69 |
Correct |
486 ms |
69680 KB |
Output is correct |
70 |
Correct |
256 ms |
88740 KB |
Output is correct |
71 |
Correct |
249 ms |
74028 KB |
Output is correct |
72 |
Correct |
270 ms |
70100 KB |
Output is correct |
73 |
Correct |
290 ms |
88704 KB |
Output is correct |
74 |
Correct |
257 ms |
74068 KB |
Output is correct |
75 |
Correct |
255 ms |
70096 KB |
Output is correct |
76 |
Correct |
307 ms |
89304 KB |
Output is correct |
77 |
Correct |
467 ms |
89204 KB |
Output is correct |
78 |
Correct |
258 ms |
89076 KB |
Output is correct |
79 |
Correct |
174 ms |
7212 KB |
Output is correct |
80 |
Correct |
187 ms |
6832 KB |
Output is correct |
81 |
Correct |
145 ms |
6860 KB |
Output is correct |
82 |
Correct |
320 ms |
89292 KB |
Output is correct |
83 |
Correct |
317 ms |
87576 KB |
Output is correct |
84 |
Correct |
462 ms |
89184 KB |
Output is correct |
85 |
Correct |
454 ms |
87496 KB |
Output is correct |
86 |
Correct |
255 ms |
89064 KB |
Output is correct |
87 |
Correct |
266 ms |
87808 KB |
Output is correct |
88 |
Correct |
176 ms |
7272 KB |
Output is correct |
89 |
Correct |
177 ms |
7320 KB |
Output is correct |
90 |
Correct |
199 ms |
6952 KB |
Output is correct |
91 |
Correct |
228 ms |
6900 KB |
Output is correct |
92 |
Correct |
144 ms |
6864 KB |
Output is correct |
93 |
Correct |
149 ms |
6860 KB |
Output is correct |
94 |
Correct |
258 ms |
59656 KB |
Output is correct |
95 |
Correct |
265 ms |
53352 KB |
Output is correct |
96 |
Correct |
423 ms |
59320 KB |
Output is correct |
97 |
Correct |
444 ms |
54268 KB |
Output is correct |
98 |
Correct |
221 ms |
59452 KB |
Output is correct |
99 |
Correct |
210 ms |
53836 KB |
Output is correct |
100 |
Correct |
171 ms |
7260 KB |
Output is correct |
101 |
Correct |
184 ms |
7368 KB |
Output is correct |
102 |
Correct |
179 ms |
6876 KB |
Output is correct |
103 |
Correct |
176 ms |
6948 KB |
Output is correct |
104 |
Correct |
142 ms |
6972 KB |
Output is correct |
105 |
Correct |
147 ms |
6892 KB |
Output is correct |
106 |
Correct |
294 ms |
74232 KB |
Output is correct |
107 |
Correct |
297 ms |
70536 KB |
Output is correct |
108 |
Correct |
464 ms |
74572 KB |
Output is correct |
109 |
Correct |
479 ms |
70468 KB |
Output is correct |
110 |
Correct |
246 ms |
74648 KB |
Output is correct |
111 |
Correct |
252 ms |
70744 KB |
Output is correct |
112 |
Correct |
186 ms |
7372 KB |
Output is correct |
113 |
Correct |
180 ms |
7300 KB |
Output is correct |
114 |
Correct |
191 ms |
6940 KB |
Output is correct |
115 |
Correct |
196 ms |
6944 KB |
Output is correct |
116 |
Correct |
150 ms |
6848 KB |
Output is correct |
117 |
Correct |
147 ms |
6944 KB |
Output is correct |
118 |
Correct |
246 ms |
88364 KB |
Output is correct |
119 |
Correct |
249 ms |
73784 KB |
Output is correct |
120 |
Correct |
244 ms |
69732 KB |
Output is correct |
121 |
Correct |
257 ms |
88400 KB |
Output is correct |
122 |
Correct |
260 ms |
73612 KB |
Output is correct |
123 |
Correct |
245 ms |
69580 KB |
Output is correct |
124 |
Correct |
247 ms |
88388 KB |
Output is correct |
125 |
Correct |
242 ms |
73936 KB |
Output is correct |
126 |
Correct |
241 ms |
69548 KB |
Output is correct |