// بِسْمِ اللَّهِ الرَّحْمَنِ الرَّحِيمِ
// Written by Ilia Rahbar
// #pragma GCC optimize ("O3,no-stack-protector,unroll-loops,fast-math")
// #pragma GCC target ("abm,bmi,bmi2,tbm,avx2")
#include <bits/stdc++.h>
using namespace std;
#define int int64_t
#define sz(x) int(x.size())
#define ai(x) array <int, x>
#define be(x) x.begin(), x.end()
#define pb push_back
#define el '\n'
#define sp ' '
#define fi first
#define se second
const int M = 1e9 + 7, N = 1e6 + 100;
int n, m, q, u, ans, v, vs[N], t, sq = 100, dp[N];
bool av[N];
vector <int> g[N], in;
vector <ai(2)> f[N], uni;
void mrg(vector <ai(2)> &a, vector <ai(2)> &b)
{
uni.clear();
for (int p1 = 0, p2 = 0; p1 < sz(a) || p2 < sz(b); )
{
if (p1 < sz(a))
{
if (p2 < sz(b))
{
if (a[p1][0] > b[p2][0])
uni.pb(a[p1++]);
else
uni.pb(b[p2++]);
}
else
uni.pb(a[p1++]);
}
else
uni.pb(b[p2++]);
}
b.clear();
for (auto [x, y] : uni)
if (!vs[y])
vs[y] = 1, b.pb({x, y});
for (auto [x, y] : uni)
vs[y] = 0;
if (sz(b) > sq)
b.resize(sq);
}
int32_t main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
cin >> n >> m >> q;
while (m--)
cin >> u >> v, g[u].pb(v);
for (int i = 1; i <= n; i++)
f[i].pb({0, i});
for (int i = 1; i <= n; i++)
{
for (int j = 0; j < sz(f[i]); j++)
f[i][j][0]++;
for (auto j : g[i])
mrg(f[i], f[j]);
for (int j = 0; j < sz(f[i]); j++)
f[i][j][0]--;
}
while (q--)
{
cin >> u >> t;
in.clear();
ans = -1;
for (int i = 0; i < t; i++)
cin >> v, in.pb(v), av[v] = 1;
for (auto [x, y] : f[u])
if (!av[y])
{
ans = x;
break;
}
if (t >= sq && ans == -1)
{
fill(dp, dp + u + 1, -M);
for (int i = 1; i <= u; i++)
{
if (!av[i])
dp[i] = max(dp[i], int(0));
for (auto j : g[i])
dp[j] = max(dp[j], dp[i] + 1);
}
ans = dp[u];
}
cout << (ans < 0 ? -1 : ans) << el;
for (auto i : in)
av[i] = 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
47188 KB |
Output is correct |
2 |
Correct |
20 ms |
47276 KB |
Output is correct |
3 |
Correct |
20 ms |
47196 KB |
Output is correct |
4 |
Correct |
23 ms |
47252 KB |
Output is correct |
5 |
Correct |
22 ms |
48212 KB |
Output is correct |
6 |
Correct |
22 ms |
48240 KB |
Output is correct |
7 |
Correct |
22 ms |
48200 KB |
Output is correct |
8 |
Correct |
26 ms |
49216 KB |
Output is correct |
9 |
Correct |
24 ms |
49236 KB |
Output is correct |
10 |
Correct |
26 ms |
49308 KB |
Output is correct |
11 |
Correct |
23 ms |
49236 KB |
Output is correct |
12 |
Correct |
24 ms |
48848 KB |
Output is correct |
13 |
Correct |
24 ms |
49196 KB |
Output is correct |
14 |
Correct |
23 ms |
48536 KB |
Output is correct |
15 |
Correct |
23 ms |
48468 KB |
Output is correct |
16 |
Correct |
24 ms |
48596 KB |
Output is correct |
17 |
Correct |
22 ms |
48852 KB |
Output is correct |
18 |
Correct |
27 ms |
48456 KB |
Output is correct |
19 |
Correct |
23 ms |
48816 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
47188 KB |
Output is correct |
2 |
Correct |
20 ms |
47276 KB |
Output is correct |
3 |
Correct |
20 ms |
47196 KB |
Output is correct |
4 |
Correct |
23 ms |
47252 KB |
Output is correct |
5 |
Correct |
22 ms |
48212 KB |
Output is correct |
6 |
Correct |
22 ms |
48240 KB |
Output is correct |
7 |
Correct |
22 ms |
48200 KB |
Output is correct |
8 |
Correct |
26 ms |
49216 KB |
Output is correct |
9 |
Correct |
24 ms |
49236 KB |
Output is correct |
10 |
Correct |
26 ms |
49308 KB |
Output is correct |
11 |
Correct |
23 ms |
49236 KB |
Output is correct |
12 |
Correct |
24 ms |
48848 KB |
Output is correct |
13 |
Correct |
24 ms |
49196 KB |
Output is correct |
14 |
Correct |
23 ms |
48536 KB |
Output is correct |
15 |
Correct |
23 ms |
48468 KB |
Output is correct |
16 |
Correct |
24 ms |
48596 KB |
Output is correct |
17 |
Correct |
22 ms |
48852 KB |
Output is correct |
18 |
Correct |
27 ms |
48456 KB |
Output is correct |
19 |
Correct |
23 ms |
48816 KB |
Output is correct |
20 |
Correct |
303 ms |
51764 KB |
Output is correct |
21 |
Correct |
297 ms |
51812 KB |
Output is correct |
22 |
Correct |
299 ms |
51664 KB |
Output is correct |
23 |
Correct |
350 ms |
51700 KB |
Output is correct |
24 |
Correct |
490 ms |
240188 KB |
Output is correct |
25 |
Correct |
486 ms |
227060 KB |
Output is correct |
26 |
Correct |
490 ms |
228036 KB |
Output is correct |
27 |
Correct |
524 ms |
255084 KB |
Output is correct |
28 |
Correct |
520 ms |
255148 KB |
Output is correct |
29 |
Correct |
507 ms |
255900 KB |
Output is correct |
30 |
Correct |
485 ms |
254380 KB |
Output is correct |
31 |
Correct |
508 ms |
280508 KB |
Output is correct |
32 |
Correct |
510 ms |
255044 KB |
Output is correct |
33 |
Correct |
387 ms |
185560 KB |
Output is correct |
34 |
Correct |
392 ms |
217524 KB |
Output is correct |
35 |
Correct |
373 ms |
184972 KB |
Output is correct |
36 |
Correct |
451 ms |
219136 KB |
Output is correct |
37 |
Correct |
452 ms |
245708 KB |
Output is correct |
38 |
Correct |
443 ms |
220204 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
20 ms |
47188 KB |
Output is correct |
2 |
Correct |
20 ms |
47276 KB |
Output is correct |
3 |
Correct |
20 ms |
47196 KB |
Output is correct |
4 |
Correct |
23 ms |
47252 KB |
Output is correct |
5 |
Correct |
22 ms |
48212 KB |
Output is correct |
6 |
Correct |
22 ms |
48240 KB |
Output is correct |
7 |
Correct |
22 ms |
48200 KB |
Output is correct |
8 |
Correct |
26 ms |
49216 KB |
Output is correct |
9 |
Correct |
24 ms |
49236 KB |
Output is correct |
10 |
Correct |
26 ms |
49308 KB |
Output is correct |
11 |
Correct |
23 ms |
49236 KB |
Output is correct |
12 |
Correct |
24 ms |
48848 KB |
Output is correct |
13 |
Correct |
24 ms |
49196 KB |
Output is correct |
14 |
Correct |
23 ms |
48536 KB |
Output is correct |
15 |
Correct |
23 ms |
48468 KB |
Output is correct |
16 |
Correct |
24 ms |
48596 KB |
Output is correct |
17 |
Correct |
22 ms |
48852 KB |
Output is correct |
18 |
Correct |
27 ms |
48456 KB |
Output is correct |
19 |
Correct |
23 ms |
48816 KB |
Output is correct |
20 |
Correct |
303 ms |
51764 KB |
Output is correct |
21 |
Correct |
297 ms |
51812 KB |
Output is correct |
22 |
Correct |
299 ms |
51664 KB |
Output is correct |
23 |
Correct |
350 ms |
51700 KB |
Output is correct |
24 |
Correct |
490 ms |
240188 KB |
Output is correct |
25 |
Correct |
486 ms |
227060 KB |
Output is correct |
26 |
Correct |
490 ms |
228036 KB |
Output is correct |
27 |
Correct |
524 ms |
255084 KB |
Output is correct |
28 |
Correct |
520 ms |
255148 KB |
Output is correct |
29 |
Correct |
507 ms |
255900 KB |
Output is correct |
30 |
Correct |
485 ms |
254380 KB |
Output is correct |
31 |
Correct |
508 ms |
280508 KB |
Output is correct |
32 |
Correct |
510 ms |
255044 KB |
Output is correct |
33 |
Correct |
387 ms |
185560 KB |
Output is correct |
34 |
Correct |
392 ms |
217524 KB |
Output is correct |
35 |
Correct |
373 ms |
184972 KB |
Output is correct |
36 |
Correct |
451 ms |
219136 KB |
Output is correct |
37 |
Correct |
452 ms |
245708 KB |
Output is correct |
38 |
Correct |
443 ms |
220204 KB |
Output is correct |
39 |
Correct |
511 ms |
240248 KB |
Output is correct |
40 |
Correct |
492 ms |
226376 KB |
Output is correct |
41 |
Correct |
495 ms |
233672 KB |
Output is correct |
42 |
Correct |
483 ms |
232284 KB |
Output is correct |
43 |
Correct |
499 ms |
232752 KB |
Output is correct |
44 |
Correct |
315 ms |
52344 KB |
Output is correct |
45 |
Correct |
304 ms |
52036 KB |
Output is correct |
46 |
Correct |
306 ms |
51952 KB |
Output is correct |
47 |
Correct |
301 ms |
51916 KB |
Output is correct |
48 |
Correct |
298 ms |
51920 KB |
Output is correct |
49 |
Correct |
562 ms |
254996 KB |
Output is correct |
50 |
Correct |
745 ms |
255200 KB |
Output is correct |
51 |
Correct |
318 ms |
52292 KB |
Output is correct |
52 |
Correct |
364 ms |
51944 KB |
Output is correct |
53 |
Correct |
501 ms |
218252 KB |
Output is correct |
54 |
Correct |
491 ms |
239372 KB |
Output is correct |
55 |
Correct |
535 ms |
218828 KB |
Output is correct |
56 |
Correct |
468 ms |
254184 KB |
Output is correct |
57 |
Correct |
317 ms |
52232 KB |
Output is correct |
58 |
Correct |
325 ms |
52308 KB |
Output is correct |
59 |
Correct |
378 ms |
51956 KB |
Output is correct |
60 |
Correct |
372 ms |
51936 KB |
Output is correct |
61 |
Correct |
556 ms |
255188 KB |
Output is correct |
62 |
Correct |
522 ms |
219572 KB |
Output is correct |
63 |
Correct |
480 ms |
240520 KB |
Output is correct |
64 |
Correct |
646 ms |
255176 KB |
Output is correct |
65 |
Correct |
584 ms |
219108 KB |
Output is correct |
66 |
Correct |
451 ms |
238300 KB |
Output is correct |
67 |
Correct |
753 ms |
255176 KB |
Output is correct |
68 |
Correct |
650 ms |
219580 KB |
Output is correct |
69 |
Correct |
479 ms |
241516 KB |
Output is correct |
70 |
Correct |
509 ms |
255300 KB |
Output is correct |
71 |
Correct |
449 ms |
219480 KB |
Output is correct |
72 |
Correct |
462 ms |
244312 KB |
Output is correct |
73 |
Correct |
520 ms |
255284 KB |
Output is correct |
74 |
Correct |
455 ms |
219340 KB |
Output is correct |
75 |
Correct |
500 ms |
253600 KB |
Output is correct |
76 |
Correct |
557 ms |
254976 KB |
Output is correct |
77 |
Correct |
485 ms |
254412 KB |
Output is correct |
78 |
Correct |
491 ms |
254896 KB |
Output is correct |
79 |
Correct |
326 ms |
52336 KB |
Output is correct |
80 |
Correct |
302 ms |
51916 KB |
Output is correct |
81 |
Correct |
301 ms |
51952 KB |
Output is correct |
82 |
Correct |
553 ms |
254316 KB |
Output is correct |
83 |
Correct |
557 ms |
279696 KB |
Output is correct |
84 |
Correct |
498 ms |
253720 KB |
Output is correct |
85 |
Correct |
515 ms |
293336 KB |
Output is correct |
86 |
Correct |
498 ms |
254168 KB |
Output is correct |
87 |
Correct |
545 ms |
275020 KB |
Output is correct |
88 |
Correct |
330 ms |
52304 KB |
Output is correct |
89 |
Correct |
321 ms |
52308 KB |
Output is correct |
90 |
Correct |
303 ms |
51916 KB |
Output is correct |
91 |
Correct |
299 ms |
51876 KB |
Output is correct |
92 |
Correct |
296 ms |
51912 KB |
Output is correct |
93 |
Correct |
297 ms |
51916 KB |
Output is correct |
94 |
Correct |
417 ms |
185828 KB |
Output is correct |
95 |
Correct |
431 ms |
224784 KB |
Output is correct |
96 |
Correct |
376 ms |
184728 KB |
Output is correct |
97 |
Correct |
403 ms |
227792 KB |
Output is correct |
98 |
Correct |
426 ms |
185840 KB |
Output is correct |
99 |
Correct |
412 ms |
224116 KB |
Output is correct |
100 |
Correct |
376 ms |
52076 KB |
Output is correct |
101 |
Correct |
377 ms |
52188 KB |
Output is correct |
102 |
Correct |
352 ms |
51776 KB |
Output is correct |
103 |
Correct |
365 ms |
51796 KB |
Output is correct |
104 |
Correct |
353 ms |
51788 KB |
Output is correct |
105 |
Correct |
359 ms |
51764 KB |
Output is correct |
106 |
Correct |
493 ms |
218592 KB |
Output is correct |
107 |
Correct |
525 ms |
248952 KB |
Output is correct |
108 |
Correct |
463 ms |
219124 KB |
Output is correct |
109 |
Correct |
455 ms |
236632 KB |
Output is correct |
110 |
Correct |
473 ms |
219604 KB |
Output is correct |
111 |
Correct |
450 ms |
233416 KB |
Output is correct |
112 |
Correct |
326 ms |
52332 KB |
Output is correct |
113 |
Correct |
320 ms |
52300 KB |
Output is correct |
114 |
Correct |
306 ms |
51784 KB |
Output is correct |
115 |
Correct |
310 ms |
51928 KB |
Output is correct |
116 |
Correct |
299 ms |
51932 KB |
Output is correct |
117 |
Correct |
307 ms |
51840 KB |
Output is correct |
118 |
Correct |
532 ms |
254352 KB |
Output is correct |
119 |
Correct |
529 ms |
218784 KB |
Output is correct |
120 |
Correct |
482 ms |
253380 KB |
Output is correct |
121 |
Correct |
535 ms |
254420 KB |
Output is correct |
122 |
Correct |
504 ms |
218316 KB |
Output is correct |
123 |
Correct |
462 ms |
249240 KB |
Output is correct |
124 |
Correct |
530 ms |
254204 KB |
Output is correct |
125 |
Correct |
479 ms |
219124 KB |
Output is correct |
126 |
Correct |
467 ms |
251024 KB |
Output is correct |