#include <bits/stdc++.h>
#define ALL(x) x.begin(), x.end()
#define pii pair<int,int>
const int MAXN = 1e5 + 1;
const int SQRT = 30;
using namespace std;
#pragma GCC optimize("Ofast,unroll-loops")
#pragma GCC target("avx2,popcnt,lzcnt,abm,bmi,bmi2,fma,tune=native")
int block[MAXN], dp[MAXN], order[MAXN], tempo;
vector<int> trafo[MAXN];
vector<pii> best[MAXN];
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int main(){
ios::sync_with_stdio(false);
int n, m, q;
scanf("%d %d %d", &n, &m, &q);
for(int i=0, u, v; i<m; i++)
{
scanf("%d %d", &u, &v);
trafo[v].push_back(u);
dp[u]++;
}
deque<int> fila;
for(int i=1; i<=n; i++) if(!dp[i]) fila.push_back(i);
int od = n;
while(!fila.empty())
{
int u = fila.front(); fila.pop_front();
order[--od] = u;
shuffle(ALL(trafo[u]), rng);
for(int v : trafo[u])
if(--dp[v] == 0)
fila.push_back(v);
}
order[n] = -1;
for(int u : order)
{
if(u == -1) break;
best[u].push_back(pii(0, u));
for(auto v : trafo[u]){
for(auto [x, w] : best[v])
best[u].push_back(pii(x-1, w));
if(best[u].size() >= 316)
{
sort(ALL(best[u]));
best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
}
}
sort(ALL(best[u]));
best[u].resize(min(SQRT, (int)(unique(ALL(best[u])) - best[u].begin())));
}
int t, y;
while(q--)
{
tempo++;
scanf("%d %d", &t, &y);
for(int i=0, x; i<y; i++)
{
scanf("%d", &x);
block[x] = tempo;
}
int ans = -1;
for(auto [x, w] : best[t])
if(block[w] != tempo)
{
ans = -x;
break;
}
if(ans == -1) for(int u : order)
{
dp[u] = (block[u] == tempo ? -1 : 0);
for(auto v : trafo[u])
if(~dp[v])
dp[u] = max(dp[u], dp[v]+1);
if(u == t){ ans = dp[u]; break; }
}
printf("%d\n", ans);
}
return 0;
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:18:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
18 | scanf("%d %d %d", &n, &m, &q);
| ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
bitaro.cpp:22:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
22 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:65:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
65 | scanf("%d %d", &t, &y);
| ~~~~~^~~~~~~~~~~~~~~~~
bitaro.cpp:69:9: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
69 | scanf("%d", &x);
| ~~~~~^~~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5088 KB |
Output is correct |
3 |
Correct |
3 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5468 KB |
Output is correct |
7 |
Correct |
3 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5720 KB |
Output is correct |
9 |
Correct |
4 ms |
5724 KB |
Output is correct |
10 |
Correct |
4 ms |
5724 KB |
Output is correct |
11 |
Correct |
5 ms |
5772 KB |
Output is correct |
12 |
Correct |
4 ms |
5724 KB |
Output is correct |
13 |
Correct |
5 ms |
5724 KB |
Output is correct |
14 |
Correct |
4 ms |
5468 KB |
Output is correct |
15 |
Correct |
4 ms |
5468 KB |
Output is correct |
16 |
Correct |
4 ms |
5636 KB |
Output is correct |
17 |
Correct |
4 ms |
5468 KB |
Output is correct |
18 |
Correct |
4 ms |
5468 KB |
Output is correct |
19 |
Correct |
4 ms |
5468 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5088 KB |
Output is correct |
3 |
Correct |
3 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5468 KB |
Output is correct |
7 |
Correct |
3 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5720 KB |
Output is correct |
9 |
Correct |
4 ms |
5724 KB |
Output is correct |
10 |
Correct |
4 ms |
5724 KB |
Output is correct |
11 |
Correct |
5 ms |
5772 KB |
Output is correct |
12 |
Correct |
4 ms |
5724 KB |
Output is correct |
13 |
Correct |
5 ms |
5724 KB |
Output is correct |
14 |
Correct |
4 ms |
5468 KB |
Output is correct |
15 |
Correct |
4 ms |
5468 KB |
Output is correct |
16 |
Correct |
4 ms |
5636 KB |
Output is correct |
17 |
Correct |
4 ms |
5468 KB |
Output is correct |
18 |
Correct |
4 ms |
5468 KB |
Output is correct |
19 |
Correct |
4 ms |
5468 KB |
Output is correct |
20 |
Correct |
226 ms |
11812 KB |
Output is correct |
21 |
Correct |
219 ms |
11760 KB |
Output is correct |
22 |
Correct |
219 ms |
11808 KB |
Output is correct |
23 |
Correct |
222 ms |
11772 KB |
Output is correct |
24 |
Correct |
247 ms |
59728 KB |
Output is correct |
25 |
Correct |
273 ms |
60136 KB |
Output is correct |
26 |
Correct |
242 ms |
59768 KB |
Output is correct |
27 |
Correct |
220 ms |
69184 KB |
Output is correct |
28 |
Correct |
203 ms |
69200 KB |
Output is correct |
29 |
Correct |
206 ms |
69204 KB |
Output is correct |
30 |
Correct |
205 ms |
69304 KB |
Output is correct |
31 |
Correct |
236 ms |
68116 KB |
Output is correct |
32 |
Correct |
266 ms |
69200 KB |
Output is correct |
33 |
Correct |
182 ms |
54868 KB |
Output is correct |
34 |
Correct |
229 ms |
52560 KB |
Output is correct |
35 |
Correct |
180 ms |
54280 KB |
Output is correct |
36 |
Correct |
198 ms |
60804 KB |
Output is correct |
37 |
Correct |
254 ms |
58708 KB |
Output is correct |
38 |
Correct |
189 ms |
60288 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
3 ms |
4956 KB |
Output is correct |
2 |
Correct |
2 ms |
5088 KB |
Output is correct |
3 |
Correct |
3 ms |
4956 KB |
Output is correct |
4 |
Correct |
2 ms |
4956 KB |
Output is correct |
5 |
Correct |
4 ms |
5716 KB |
Output is correct |
6 |
Correct |
4 ms |
5468 KB |
Output is correct |
7 |
Correct |
3 ms |
5468 KB |
Output is correct |
8 |
Correct |
4 ms |
5720 KB |
Output is correct |
9 |
Correct |
4 ms |
5724 KB |
Output is correct |
10 |
Correct |
4 ms |
5724 KB |
Output is correct |
11 |
Correct |
5 ms |
5772 KB |
Output is correct |
12 |
Correct |
4 ms |
5724 KB |
Output is correct |
13 |
Correct |
5 ms |
5724 KB |
Output is correct |
14 |
Correct |
4 ms |
5468 KB |
Output is correct |
15 |
Correct |
4 ms |
5468 KB |
Output is correct |
16 |
Correct |
4 ms |
5636 KB |
Output is correct |
17 |
Correct |
4 ms |
5468 KB |
Output is correct |
18 |
Correct |
4 ms |
5468 KB |
Output is correct |
19 |
Correct |
4 ms |
5468 KB |
Output is correct |
20 |
Correct |
226 ms |
11812 KB |
Output is correct |
21 |
Correct |
219 ms |
11760 KB |
Output is correct |
22 |
Correct |
219 ms |
11808 KB |
Output is correct |
23 |
Correct |
222 ms |
11772 KB |
Output is correct |
24 |
Correct |
247 ms |
59728 KB |
Output is correct |
25 |
Correct |
273 ms |
60136 KB |
Output is correct |
26 |
Correct |
242 ms |
59768 KB |
Output is correct |
27 |
Correct |
220 ms |
69184 KB |
Output is correct |
28 |
Correct |
203 ms |
69200 KB |
Output is correct |
29 |
Correct |
206 ms |
69204 KB |
Output is correct |
30 |
Correct |
205 ms |
69304 KB |
Output is correct |
31 |
Correct |
236 ms |
68116 KB |
Output is correct |
32 |
Correct |
266 ms |
69200 KB |
Output is correct |
33 |
Correct |
182 ms |
54868 KB |
Output is correct |
34 |
Correct |
229 ms |
52560 KB |
Output is correct |
35 |
Correct |
180 ms |
54280 KB |
Output is correct |
36 |
Correct |
198 ms |
60804 KB |
Output is correct |
37 |
Correct |
254 ms |
58708 KB |
Output is correct |
38 |
Correct |
189 ms |
60288 KB |
Output is correct |
39 |
Correct |
278 ms |
60916 KB |
Output is correct |
40 |
Correct |
241 ms |
60016 KB |
Output is correct |
41 |
Correct |
248 ms |
60072 KB |
Output is correct |
42 |
Correct |
250 ms |
60496 KB |
Output is correct |
43 |
Correct |
231 ms |
60288 KB |
Output is correct |
44 |
Correct |
246 ms |
13028 KB |
Output is correct |
45 |
Correct |
225 ms |
12116 KB |
Output is correct |
46 |
Correct |
222 ms |
12116 KB |
Output is correct |
47 |
Correct |
219 ms |
11856 KB |
Output is correct |
48 |
Correct |
254 ms |
11724 KB |
Output is correct |
49 |
Correct |
221 ms |
69968 KB |
Output is correct |
50 |
Correct |
747 ms |
68944 KB |
Output is correct |
51 |
Correct |
234 ms |
12812 KB |
Output is correct |
52 |
Correct |
488 ms |
12116 KB |
Output is correct |
53 |
Correct |
209 ms |
61004 KB |
Output is correct |
54 |
Correct |
229 ms |
59440 KB |
Output is correct |
55 |
Correct |
696 ms |
60412 KB |
Output is correct |
56 |
Correct |
873 ms |
58812 KB |
Output is correct |
57 |
Correct |
231 ms |
12628 KB |
Output is correct |
58 |
Correct |
266 ms |
12720 KB |
Output is correct |
59 |
Correct |
436 ms |
12168 KB |
Output is correct |
60 |
Correct |
476 ms |
12024 KB |
Output is correct |
61 |
Correct |
251 ms |
68944 KB |
Output is correct |
62 |
Correct |
245 ms |
60288 KB |
Output is correct |
63 |
Correct |
268 ms |
58452 KB |
Output is correct |
64 |
Correct |
368 ms |
68944 KB |
Output is correct |
65 |
Correct |
349 ms |
60068 KB |
Output is correct |
66 |
Correct |
391 ms |
58832 KB |
Output is correct |
67 |
Correct |
486 ms |
68948 KB |
Output is correct |
68 |
Correct |
466 ms |
60340 KB |
Output is correct |
69 |
Correct |
533 ms |
58196 KB |
Output is correct |
70 |
Correct |
194 ms |
68944 KB |
Output is correct |
71 |
Correct |
178 ms |
60272 KB |
Output is correct |
72 |
Correct |
207 ms |
58448 KB |
Output is correct |
73 |
Correct |
212 ms |
68944 KB |
Output is correct |
74 |
Correct |
202 ms |
60240 KB |
Output is correct |
75 |
Correct |
230 ms |
58708 KB |
Output is correct |
76 |
Correct |
216 ms |
70820 KB |
Output is correct |
77 |
Correct |
179 ms |
69452 KB |
Output is correct |
78 |
Correct |
195 ms |
69656 KB |
Output is correct |
79 |
Correct |
225 ms |
12964 KB |
Output is correct |
80 |
Correct |
203 ms |
12368 KB |
Output is correct |
81 |
Correct |
196 ms |
11844 KB |
Output is correct |
82 |
Correct |
230 ms |
70480 KB |
Output is correct |
83 |
Correct |
254 ms |
69432 KB |
Output is correct |
84 |
Correct |
260 ms |
69460 KB |
Output is correct |
85 |
Correct |
224 ms |
68436 KB |
Output is correct |
86 |
Correct |
196 ms |
69560 KB |
Output is correct |
87 |
Correct |
223 ms |
68692 KB |
Output is correct |
88 |
Correct |
223 ms |
12960 KB |
Output is correct |
89 |
Correct |
260 ms |
12956 KB |
Output is correct |
90 |
Correct |
219 ms |
12152 KB |
Output is correct |
91 |
Correct |
208 ms |
12028 KB |
Output is correct |
92 |
Correct |
210 ms |
11860 KB |
Output is correct |
93 |
Correct |
217 ms |
11860 KB |
Output is correct |
94 |
Correct |
200 ms |
56120 KB |
Output is correct |
95 |
Correct |
207 ms |
53500 KB |
Output is correct |
96 |
Correct |
182 ms |
54868 KB |
Output is correct |
97 |
Correct |
187 ms |
53108 KB |
Output is correct |
98 |
Correct |
174 ms |
55124 KB |
Output is correct |
99 |
Correct |
186 ms |
52940 KB |
Output is correct |
100 |
Correct |
225 ms |
12792 KB |
Output is correct |
101 |
Correct |
217 ms |
12696 KB |
Output is correct |
102 |
Correct |
214 ms |
11856 KB |
Output is correct |
103 |
Correct |
211 ms |
12048 KB |
Output is correct |
104 |
Correct |
198 ms |
11856 KB |
Output is correct |
105 |
Correct |
215 ms |
11592 KB |
Output is correct |
106 |
Correct |
198 ms |
61592 KB |
Output is correct |
107 |
Correct |
219 ms |
60200 KB |
Output is correct |
108 |
Correct |
187 ms |
60752 KB |
Output is correct |
109 |
Correct |
201 ms |
58964 KB |
Output is correct |
110 |
Correct |
178 ms |
61012 KB |
Output is correct |
111 |
Correct |
201 ms |
59096 KB |
Output is correct |
112 |
Correct |
241 ms |
12884 KB |
Output is correct |
113 |
Correct |
239 ms |
12884 KB |
Output is correct |
114 |
Correct |
229 ms |
12112 KB |
Output is correct |
115 |
Correct |
217 ms |
12116 KB |
Output is correct |
116 |
Correct |
215 ms |
11856 KB |
Output is correct |
117 |
Correct |
234 ms |
11688 KB |
Output is correct |
118 |
Execution timed out |
2041 ms |
68176 KB |
Time limit exceeded |
119 |
Halted |
0 ms |
0 KB |
- |