#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N = 1e5 + 7;
const int Inf = 1e9;
vector <int> g[N];
vector <int> rg[N];
bool used[N];
int dp[N];
int ban[N];
bool have[N];
vector <pair <int, int>> best[N];
vector <int> ts;
void dfs(int u) {
used[u] = 1;
for (int v : g[u]) {
if (!used[v]) {
dfs(v);
}
}
ts.push_back(u);
}
const int K = 200;
int main() {
ios_base::sync_with_stdio(false); cin.tie(0); cout.setf(ios::fixed); cout.precision(20);
#ifdef LOCAL
freopen("input.txt", "r", stdin);
freopen("output.txt", "w", stdout);
#endif
int n, m, q;
cin >> n >> m >> q;
for (int i = 0; i < m; ++i) {
int u, v;
cin >> u >> v;
--u, --v;
g[u].push_back(v);
rg[v].push_back(u);
}
for (int i = 0; i < n; ++i) {
if (!used[i]) {
dfs(i);
}
}
for (int i = (int)ts.size() - 1; i >= 0; --i) {
int u = ts[i];
int sz = rg[u].size();
vector <int> uk(sz);
while (true) {
pair <int, int> mx = {0, u};
int id = -1;
for (int i = 0; i < sz; ++i) {
while (uk[i] < (int)best[rg[u][i]].size() && have[best[rg[u][i]][uk[i]].second]) {
++uk[i];
}
if (uk[i] < (int)best[rg[u][i]].size()) {
auto cp = best[rg[u][i]][uk[i]];
++cp.first;
if (cp > mx) {
mx = cp;
id = i;
}
}
}
if (id == -1) {
best[u].push_back(mx);
break;
} else {
best[u].push_back(mx);
++uk[id];
have[mx.second] = 1;
if ((int)best[u].size() == K) break;
}
}
for (int v : rg[u]) {
for (auto p : best[v]) {
have[p.second] = 0;
}
}
}
while (q--) {
int t;
cin >> t;
--t;
int y;
cin >> y;
vector <int> who;
for (int i = 0; i < y; ++i) {
int x;
cin >> x;
--x;
who.push_back(x);
ban[x] = 1;
}
if (y >= K) {
fill(dp, dp + n, -Inf);
dp[t] = 0;
for (int x : ts) {
for (int v : g[x]) {
dp[x] = max(dp[x], dp[v] + 1);
}
}
int ans = -1;
for (int i = 0; i < n; ++i) if (!ban[i]) ans = max(ans, dp[i]);
cout << ans << '\n';
} else {
int ans = -1;
for (auto p : best[t]) {
if (!ban[p.second]) {
ans = max(ans, p.first);
}
}
cout << ans << '\n';
}
for (int x : who) ban[x] = 0;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7420 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
11 ms |
7928 KB |
Output is correct |
6 |
Correct |
12 ms |
7928 KB |
Output is correct |
7 |
Correct |
11 ms |
7928 KB |
Output is correct |
8 |
Correct |
17 ms |
9336 KB |
Output is correct |
9 |
Correct |
16 ms |
9444 KB |
Output is correct |
10 |
Correct |
16 ms |
9336 KB |
Output is correct |
11 |
Correct |
16 ms |
9208 KB |
Output is correct |
12 |
Correct |
13 ms |
8568 KB |
Output is correct |
13 |
Correct |
15 ms |
9208 KB |
Output is correct |
14 |
Correct |
14 ms |
8604 KB |
Output is correct |
15 |
Correct |
12 ms |
8104 KB |
Output is correct |
16 |
Correct |
14 ms |
8568 KB |
Output is correct |
17 |
Correct |
14 ms |
8824 KB |
Output is correct |
18 |
Correct |
13 ms |
8412 KB |
Output is correct |
19 |
Correct |
14 ms |
8952 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7420 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
11 ms |
7928 KB |
Output is correct |
6 |
Correct |
12 ms |
7928 KB |
Output is correct |
7 |
Correct |
11 ms |
7928 KB |
Output is correct |
8 |
Correct |
17 ms |
9336 KB |
Output is correct |
9 |
Correct |
16 ms |
9444 KB |
Output is correct |
10 |
Correct |
16 ms |
9336 KB |
Output is correct |
11 |
Correct |
16 ms |
9208 KB |
Output is correct |
12 |
Correct |
13 ms |
8568 KB |
Output is correct |
13 |
Correct |
15 ms |
9208 KB |
Output is correct |
14 |
Correct |
14 ms |
8604 KB |
Output is correct |
15 |
Correct |
12 ms |
8104 KB |
Output is correct |
16 |
Correct |
14 ms |
8568 KB |
Output is correct |
17 |
Correct |
14 ms |
8824 KB |
Output is correct |
18 |
Correct |
13 ms |
8412 KB |
Output is correct |
19 |
Correct |
14 ms |
8952 KB |
Output is correct |
20 |
Correct |
448 ms |
13024 KB |
Output is correct |
21 |
Correct |
430 ms |
13300 KB |
Output is correct |
22 |
Correct |
447 ms |
13176 KB |
Output is correct |
23 |
Correct |
477 ms |
13292 KB |
Output is correct |
24 |
Correct |
853 ms |
159312 KB |
Output is correct |
25 |
Correct |
926 ms |
163824 KB |
Output is correct |
26 |
Correct |
860 ms |
163772 KB |
Output is correct |
27 |
Correct |
901 ms |
224956 KB |
Output is correct |
28 |
Correct |
897 ms |
224880 KB |
Output is correct |
29 |
Correct |
889 ms |
224704 KB |
Output is correct |
30 |
Correct |
962 ms |
219312 KB |
Output is correct |
31 |
Correct |
948 ms |
214028 KB |
Output is correct |
32 |
Correct |
917 ms |
219212 KB |
Output is correct |
33 |
Correct |
679 ms |
142772 KB |
Output is correct |
34 |
Correct |
659 ms |
123248 KB |
Output is correct |
35 |
Correct |
731 ms |
141704 KB |
Output is correct |
36 |
Correct |
870 ms |
181972 KB |
Output is correct |
37 |
Correct |
852 ms |
168980 KB |
Output is correct |
38 |
Correct |
870 ms |
182268 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
8 ms |
7420 KB |
Output is correct |
2 |
Correct |
8 ms |
7416 KB |
Output is correct |
3 |
Correct |
8 ms |
7416 KB |
Output is correct |
4 |
Correct |
8 ms |
7416 KB |
Output is correct |
5 |
Correct |
11 ms |
7928 KB |
Output is correct |
6 |
Correct |
12 ms |
7928 KB |
Output is correct |
7 |
Correct |
11 ms |
7928 KB |
Output is correct |
8 |
Correct |
17 ms |
9336 KB |
Output is correct |
9 |
Correct |
16 ms |
9444 KB |
Output is correct |
10 |
Correct |
16 ms |
9336 KB |
Output is correct |
11 |
Correct |
16 ms |
9208 KB |
Output is correct |
12 |
Correct |
13 ms |
8568 KB |
Output is correct |
13 |
Correct |
15 ms |
9208 KB |
Output is correct |
14 |
Correct |
14 ms |
8604 KB |
Output is correct |
15 |
Correct |
12 ms |
8104 KB |
Output is correct |
16 |
Correct |
14 ms |
8568 KB |
Output is correct |
17 |
Correct |
14 ms |
8824 KB |
Output is correct |
18 |
Correct |
13 ms |
8412 KB |
Output is correct |
19 |
Correct |
14 ms |
8952 KB |
Output is correct |
20 |
Correct |
448 ms |
13024 KB |
Output is correct |
21 |
Correct |
430 ms |
13300 KB |
Output is correct |
22 |
Correct |
447 ms |
13176 KB |
Output is correct |
23 |
Correct |
477 ms |
13292 KB |
Output is correct |
24 |
Correct |
853 ms |
159312 KB |
Output is correct |
25 |
Correct |
926 ms |
163824 KB |
Output is correct |
26 |
Correct |
860 ms |
163772 KB |
Output is correct |
27 |
Correct |
901 ms |
224956 KB |
Output is correct |
28 |
Correct |
897 ms |
224880 KB |
Output is correct |
29 |
Correct |
889 ms |
224704 KB |
Output is correct |
30 |
Correct |
962 ms |
219312 KB |
Output is correct |
31 |
Correct |
948 ms |
214028 KB |
Output is correct |
32 |
Correct |
917 ms |
219212 KB |
Output is correct |
33 |
Correct |
679 ms |
142772 KB |
Output is correct |
34 |
Correct |
659 ms |
123248 KB |
Output is correct |
35 |
Correct |
731 ms |
141704 KB |
Output is correct |
36 |
Correct |
870 ms |
181972 KB |
Output is correct |
37 |
Correct |
852 ms |
168980 KB |
Output is correct |
38 |
Correct |
870 ms |
182268 KB |
Output is correct |
39 |
Correct |
941 ms |
160784 KB |
Output is correct |
40 |
Correct |
870 ms |
159992 KB |
Output is correct |
41 |
Correct |
845 ms |
160340 KB |
Output is correct |
42 |
Correct |
1127 ms |
161008 KB |
Output is correct |
43 |
Correct |
849 ms |
160116 KB |
Output is correct |
44 |
Correct |
507 ms |
13880 KB |
Output is correct |
45 |
Correct |
467 ms |
13568 KB |
Output is correct |
46 |
Correct |
472 ms |
13544 KB |
Output is correct |
47 |
Correct |
483 ms |
13220 KB |
Output is correct |
48 |
Correct |
450 ms |
13140 KB |
Output is correct |
49 |
Correct |
1066 ms |
223444 KB |
Output is correct |
50 |
Correct |
988 ms |
222652 KB |
Output is correct |
51 |
Correct |
511 ms |
13980 KB |
Output is correct |
52 |
Correct |
465 ms |
13440 KB |
Output is correct |
53 |
Correct |
1051 ms |
179560 KB |
Output is correct |
54 |
Correct |
904 ms |
166952 KB |
Output is correct |
55 |
Correct |
810 ms |
179208 KB |
Output is correct |
56 |
Correct |
820 ms |
167400 KB |
Output is correct |
57 |
Correct |
505 ms |
13936 KB |
Output is correct |
58 |
Correct |
536 ms |
13944 KB |
Output is correct |
59 |
Correct |
450 ms |
13424 KB |
Output is correct |
60 |
Correct |
457 ms |
13388 KB |
Output is correct |
61 |
Correct |
1061 ms |
222708 KB |
Output is correct |
62 |
Correct |
1047 ms |
180212 KB |
Output is correct |
63 |
Correct |
1073 ms |
166212 KB |
Output is correct |
64 |
Correct |
1348 ms |
222404 KB |
Output is correct |
65 |
Correct |
1514 ms |
179116 KB |
Output is correct |
66 |
Correct |
1597 ms |
167208 KB |
Output is correct |
67 |
Correct |
1284 ms |
222580 KB |
Output is correct |
68 |
Correct |
1398 ms |
179884 KB |
Output is correct |
69 |
Correct |
1435 ms |
165344 KB |
Output is correct |
70 |
Correct |
925 ms |
222432 KB |
Output is correct |
71 |
Correct |
837 ms |
179772 KB |
Output is correct |
72 |
Correct |
840 ms |
166772 KB |
Output is correct |
73 |
Correct |
948 ms |
222404 KB |
Output is correct |
74 |
Correct |
870 ms |
179648 KB |
Output is correct |
75 |
Correct |
875 ms |
166412 KB |
Output is correct |
76 |
Correct |
1041 ms |
222748 KB |
Output is correct |
77 |
Correct |
953 ms |
222604 KB |
Output is correct |
78 |
Correct |
940 ms |
222888 KB |
Output is correct |
79 |
Correct |
495 ms |
12920 KB |
Output is correct |
80 |
Correct |
445 ms |
12776 KB |
Output is correct |
81 |
Correct |
437 ms |
12948 KB |
Output is correct |
82 |
Correct |
1032 ms |
217252 KB |
Output is correct |
83 |
Correct |
1076 ms |
212028 KB |
Output is correct |
84 |
Correct |
985 ms |
217156 KB |
Output is correct |
85 |
Correct |
1068 ms |
211736 KB |
Output is correct |
86 |
Correct |
936 ms |
217272 KB |
Output is correct |
87 |
Correct |
1014 ms |
212356 KB |
Output is correct |
88 |
Correct |
503 ms |
12864 KB |
Output is correct |
89 |
Correct |
504 ms |
12924 KB |
Output is correct |
90 |
Correct |
451 ms |
12560 KB |
Output is correct |
91 |
Correct |
457 ms |
12700 KB |
Output is correct |
92 |
Correct |
438 ms |
12664 KB |
Output is correct |
93 |
Correct |
448 ms |
12792 KB |
Output is correct |
94 |
Correct |
763 ms |
140660 KB |
Output is correct |
95 |
Correct |
718 ms |
120416 KB |
Output is correct |
96 |
Correct |
732 ms |
139964 KB |
Output is correct |
97 |
Correct |
680 ms |
122632 KB |
Output is correct |
98 |
Correct |
703 ms |
140508 KB |
Output is correct |
99 |
Correct |
646 ms |
122312 KB |
Output is correct |
100 |
Correct |
535 ms |
12900 KB |
Output is correct |
101 |
Correct |
545 ms |
13008 KB |
Output is correct |
102 |
Correct |
488 ms |
12544 KB |
Output is correct |
103 |
Correct |
493 ms |
12636 KB |
Output is correct |
104 |
Correct |
472 ms |
12664 KB |
Output is correct |
105 |
Correct |
481 ms |
12624 KB |
Output is correct |
106 |
Correct |
892 ms |
179300 KB |
Output is correct |
107 |
Correct |
889 ms |
166712 KB |
Output is correct |
108 |
Correct |
881 ms |
180296 KB |
Output is correct |
109 |
Correct |
876 ms |
166428 KB |
Output is correct |
110 |
Correct |
841 ms |
180584 KB |
Output is correct |
111 |
Correct |
858 ms |
166948 KB |
Output is correct |
112 |
Correct |
502 ms |
12536 KB |
Output is correct |
113 |
Correct |
504 ms |
12408 KB |
Output is correct |
114 |
Correct |
453 ms |
12184 KB |
Output is correct |
115 |
Correct |
457 ms |
12048 KB |
Output is correct |
116 |
Correct |
442 ms |
12280 KB |
Output is correct |
117 |
Correct |
445 ms |
12280 KB |
Output is correct |
118 |
Correct |
938 ms |
221160 KB |
Output is correct |
119 |
Correct |
816 ms |
178692 KB |
Output is correct |
120 |
Correct |
895 ms |
165076 KB |
Output is correct |
121 |
Correct |
1066 ms |
221128 KB |
Output is correct |
122 |
Correct |
922 ms |
177996 KB |
Output is correct |
123 |
Correct |
816 ms |
164760 KB |
Output is correct |
124 |
Correct |
928 ms |
221248 KB |
Output is correct |
125 |
Correct |
827 ms |
179096 KB |
Output is correct |
126 |
Correct |
820 ms |
164592 KB |
Output is correct |