#include <bits/stdc++.h>
using namespace std;
const int MAXN = 100005;
const int BLOCK = 305;
int N, M, Q;
vector<int> radj[MAXN];
int vis[MAXN], mark = 0;
int dp[MAXN];
bool cannot_visit[MAXN];
int in_ans[MAXN];
vector<pair<int, int>> ans[MAXN]; // BLOCK longest paths from a vertex (city, length)
void Read() {
ios::sync_with_stdio(0);
cin.tie(0), cout.tie(0);
cin >> N >> M >> Q;
for (int i = 0; i < M; i++) {
int S, E;
cin >> S >> E;
radj[E].emplace_back(S);
}
}
void Preprocess(int n) {
if (vis[n] == mark) return;
vis[n] = mark;
ans[n].emplace_back(n, 0);
in_ans[n] = 0;
for (auto i : radj[n]) {
Preprocess(i);
for (auto j : ans[i]) {
if (in_ans[j.first] == -1) {
in_ans[j.first] = ans[n].size();
ans[n].emplace_back(j.first, j.second + 1);
} else {
ans[n][in_ans[j.first]] = max(ans[n][in_ans[j.first]], make_pair(j.first, j.second + 1));
}
}
}
for (auto i : ans[n]) {
in_ans[i.first] = -1;
}
nth_element(begin(ans[n]), begin(ans[n]) + BLOCK, end(ans[n]),
[&](const pair<int, int> &a, const pair<int, int> &b) { return a.second > b.second; });
while (ans[n].size() > BLOCK) ans[n].pop_back();
}
void Dfs(int n) {
if (vis[n] == mark) return;
vis[n] = mark;
dp[n] = (cannot_visit[n] ? -1e9 : 0);
for (auto i : radj[n]) {
Dfs(i);
dp[n] = max(dp[n], dp[i] + 1);
}
}
void Preprocess() {
memset(in_ans, -1, sizeof(in_ans));
mark++;
for (int i = 1; i <= N; i++) {
Preprocess(i);
}
}
void Solve() {
for (int i = 0; i < Q; i++) {
int T, Y;
cin >> T >> Y;
vector<int> C(Y);
for (auto &c : C) {
cin >> c;
cannot_visit[c] = true;
}
int res = -1;
if (C.size() >= BLOCK) {
mark++; Dfs(T);
res = max(res, dp[T]) ;
} else {
for (int j = 0; j < ans[T].size(); j++) {
int u = ans[T][j].first;
if (cannot_visit[u]) continue;
res = max(res, ans[T][j].second);
}
}
for (auto c : C) {
cannot_visit[c] = false;
}
cout << res << "\n";
}
}
int main() {
Read();
Preprocess();
Solve();
return 0;
}
Compilation message
bitaro.cpp: In function 'void Solve()':
bitaro.cpp:94:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for (int j = 0; j < ans[T].size(); j++) {
~~^~~~~~~~~~~~~~~
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5376 KB |
Output is correct |
2 |
Correct |
7 ms |
5376 KB |
Output is correct |
3 |
Correct |
8 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5376 KB |
Output is correct |
5 |
Correct |
9 ms |
5888 KB |
Output is correct |
6 |
Correct |
9 ms |
5888 KB |
Output is correct |
7 |
Correct |
9 ms |
5888 KB |
Output is correct |
8 |
Correct |
17 ms |
8832 KB |
Output is correct |
9 |
Correct |
16 ms |
8832 KB |
Output is correct |
10 |
Correct |
16 ms |
8832 KB |
Output is correct |
11 |
Correct |
15 ms |
8448 KB |
Output is correct |
12 |
Correct |
12 ms |
6784 KB |
Output is correct |
13 |
Correct |
15 ms |
8192 KB |
Output is correct |
14 |
Correct |
13 ms |
7424 KB |
Output is correct |
15 |
Correct |
11 ms |
6400 KB |
Output is correct |
16 |
Correct |
13 ms |
7424 KB |
Output is correct |
17 |
Correct |
14 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
6656 KB |
Output is correct |
19 |
Correct |
14 ms |
7680 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5376 KB |
Output is correct |
2 |
Correct |
7 ms |
5376 KB |
Output is correct |
3 |
Correct |
8 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5376 KB |
Output is correct |
5 |
Correct |
9 ms |
5888 KB |
Output is correct |
6 |
Correct |
9 ms |
5888 KB |
Output is correct |
7 |
Correct |
9 ms |
5888 KB |
Output is correct |
8 |
Correct |
17 ms |
8832 KB |
Output is correct |
9 |
Correct |
16 ms |
8832 KB |
Output is correct |
10 |
Correct |
16 ms |
8832 KB |
Output is correct |
11 |
Correct |
15 ms |
8448 KB |
Output is correct |
12 |
Correct |
12 ms |
6784 KB |
Output is correct |
13 |
Correct |
15 ms |
8192 KB |
Output is correct |
14 |
Correct |
13 ms |
7424 KB |
Output is correct |
15 |
Correct |
11 ms |
6400 KB |
Output is correct |
16 |
Correct |
13 ms |
7424 KB |
Output is correct |
17 |
Correct |
14 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
6656 KB |
Output is correct |
19 |
Correct |
14 ms |
7680 KB |
Output is correct |
20 |
Correct |
336 ms |
10056 KB |
Output is correct |
21 |
Correct |
323 ms |
9944 KB |
Output is correct |
22 |
Correct |
328 ms |
10024 KB |
Output is correct |
23 |
Correct |
381 ms |
9976 KB |
Output is correct |
24 |
Correct |
862 ms |
258040 KB |
Output is correct |
25 |
Correct |
890 ms |
267384 KB |
Output is correct |
26 |
Correct |
869 ms |
265848 KB |
Output is correct |
27 |
Correct |
983 ms |
414052 KB |
Output is correct |
28 |
Correct |
983 ms |
414168 KB |
Output is correct |
29 |
Correct |
991 ms |
415176 KB |
Output is correct |
30 |
Correct |
1016 ms |
410644 KB |
Output is correct |
31 |
Correct |
1095 ms |
398712 KB |
Output is correct |
32 |
Correct |
1016 ms |
410876 KB |
Output is correct |
33 |
Correct |
713 ms |
253076 KB |
Output is correct |
34 |
Correct |
777 ms |
273272 KB |
Output is correct |
35 |
Correct |
686 ms |
251256 KB |
Output is correct |
36 |
Correct |
854 ms |
332024 KB |
Output is correct |
37 |
Correct |
933 ms |
303744 KB |
Output is correct |
38 |
Correct |
847 ms |
333032 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
7 ms |
5376 KB |
Output is correct |
2 |
Correct |
7 ms |
5376 KB |
Output is correct |
3 |
Correct |
8 ms |
5376 KB |
Output is correct |
4 |
Correct |
7 ms |
5376 KB |
Output is correct |
5 |
Correct |
9 ms |
5888 KB |
Output is correct |
6 |
Correct |
9 ms |
5888 KB |
Output is correct |
7 |
Correct |
9 ms |
5888 KB |
Output is correct |
8 |
Correct |
17 ms |
8832 KB |
Output is correct |
9 |
Correct |
16 ms |
8832 KB |
Output is correct |
10 |
Correct |
16 ms |
8832 KB |
Output is correct |
11 |
Correct |
15 ms |
8448 KB |
Output is correct |
12 |
Correct |
12 ms |
6784 KB |
Output is correct |
13 |
Correct |
15 ms |
8192 KB |
Output is correct |
14 |
Correct |
13 ms |
7424 KB |
Output is correct |
15 |
Correct |
11 ms |
6400 KB |
Output is correct |
16 |
Correct |
13 ms |
7424 KB |
Output is correct |
17 |
Correct |
14 ms |
7680 KB |
Output is correct |
18 |
Correct |
11 ms |
6656 KB |
Output is correct |
19 |
Correct |
14 ms |
7680 KB |
Output is correct |
20 |
Correct |
336 ms |
10056 KB |
Output is correct |
21 |
Correct |
323 ms |
9944 KB |
Output is correct |
22 |
Correct |
328 ms |
10024 KB |
Output is correct |
23 |
Correct |
381 ms |
9976 KB |
Output is correct |
24 |
Correct |
862 ms |
258040 KB |
Output is correct |
25 |
Correct |
890 ms |
267384 KB |
Output is correct |
26 |
Correct |
869 ms |
265848 KB |
Output is correct |
27 |
Correct |
983 ms |
414052 KB |
Output is correct |
28 |
Correct |
983 ms |
414168 KB |
Output is correct |
29 |
Correct |
991 ms |
415176 KB |
Output is correct |
30 |
Correct |
1016 ms |
410644 KB |
Output is correct |
31 |
Correct |
1095 ms |
398712 KB |
Output is correct |
32 |
Correct |
1016 ms |
410876 KB |
Output is correct |
33 |
Correct |
713 ms |
253076 KB |
Output is correct |
34 |
Correct |
777 ms |
273272 KB |
Output is correct |
35 |
Correct |
686 ms |
251256 KB |
Output is correct |
36 |
Correct |
854 ms |
332024 KB |
Output is correct |
37 |
Correct |
933 ms |
303744 KB |
Output is correct |
38 |
Correct |
847 ms |
333032 KB |
Output is correct |
39 |
Correct |
1030 ms |
261792 KB |
Output is correct |
40 |
Correct |
945 ms |
262008 KB |
Output is correct |
41 |
Correct |
988 ms |
264312 KB |
Output is correct |
42 |
Correct |
933 ms |
262904 KB |
Output is correct |
43 |
Correct |
923 ms |
263184 KB |
Output is correct |
44 |
Correct |
386 ms |
10360 KB |
Output is correct |
45 |
Correct |
339 ms |
10104 KB |
Output is correct |
46 |
Correct |
326 ms |
9976 KB |
Output is correct |
47 |
Correct |
365 ms |
10024 KB |
Output is correct |
48 |
Correct |
328 ms |
9976 KB |
Output is correct |
49 |
Correct |
1218 ms |
411512 KB |
Output is correct |
50 |
Correct |
1125 ms |
410748 KB |
Output is correct |
51 |
Correct |
395 ms |
12536 KB |
Output is correct |
52 |
Correct |
338 ms |
11896 KB |
Output is correct |
53 |
Correct |
1043 ms |
334072 KB |
Output is correct |
54 |
Correct |
1109 ms |
308088 KB |
Output is correct |
55 |
Correct |
951 ms |
333304 KB |
Output is correct |
56 |
Correct |
1024 ms |
309112 KB |
Output is correct |
57 |
Correct |
399 ms |
12604 KB |
Output is correct |
58 |
Correct |
390 ms |
12536 KB |
Output is correct |
59 |
Correct |
328 ms |
11896 KB |
Output is correct |
60 |
Correct |
326 ms |
11732 KB |
Output is correct |
61 |
Correct |
1337 ms |
418552 KB |
Output is correct |
62 |
Correct |
1080 ms |
335096 KB |
Output is correct |
63 |
Correct |
1080 ms |
306808 KB |
Output is correct |
64 |
Correct |
1741 ms |
418552 KB |
Output is correct |
65 |
Correct |
1300 ms |
333432 KB |
Output is correct |
66 |
Correct |
1250 ms |
310136 KB |
Output is correct |
67 |
Correct |
1115 ms |
413560 KB |
Output is correct |
68 |
Correct |
943 ms |
334600 KB |
Output is correct |
69 |
Correct |
998 ms |
303692 KB |
Output is correct |
70 |
Correct |
1147 ms |
418040 KB |
Output is correct |
71 |
Correct |
980 ms |
334968 KB |
Output is correct |
72 |
Correct |
1057 ms |
307832 KB |
Output is correct |
73 |
Correct |
1197 ms |
418428 KB |
Output is correct |
74 |
Correct |
999 ms |
335188 KB |
Output is correct |
75 |
Correct |
1068 ms |
308320 KB |
Output is correct |
76 |
Correct |
1217 ms |
415044 KB |
Output is correct |
77 |
Correct |
1106 ms |
413688 KB |
Output is correct |
78 |
Correct |
1147 ms |
418296 KB |
Output is correct |
79 |
Correct |
399 ms |
12792 KB |
Output is correct |
80 |
Correct |
334 ms |
11772 KB |
Output is correct |
81 |
Correct |
328 ms |
11512 KB |
Output is correct |
82 |
Correct |
1234 ms |
414584 KB |
Output is correct |
83 |
Correct |
1337 ms |
401996 KB |
Output is correct |
84 |
Correct |
1193 ms |
413276 KB |
Output is correct |
85 |
Correct |
1251 ms |
401532 KB |
Output is correct |
86 |
Correct |
1149 ms |
414176 KB |
Output is correct |
87 |
Correct |
1263 ms |
402092 KB |
Output is correct |
88 |
Correct |
391 ms |
12796 KB |
Output is correct |
89 |
Correct |
397 ms |
12792 KB |
Output is correct |
90 |
Correct |
328 ms |
11768 KB |
Output is correct |
91 |
Correct |
339 ms |
11768 KB |
Output is correct |
92 |
Correct |
324 ms |
11384 KB |
Output is correct |
93 |
Correct |
326 ms |
11424 KB |
Output is correct |
94 |
Correct |
860 ms |
257144 KB |
Output is correct |
95 |
Correct |
928 ms |
288248 KB |
Output is correct |
96 |
Correct |
762 ms |
254456 KB |
Output is correct |
97 |
Correct |
861 ms |
291448 KB |
Output is correct |
98 |
Correct |
809 ms |
255852 KB |
Output is correct |
99 |
Correct |
856 ms |
284924 KB |
Output is correct |
100 |
Correct |
444 ms |
12792 KB |
Output is correct |
101 |
Correct |
442 ms |
12792 KB |
Output is correct |
102 |
Correct |
384 ms |
12024 KB |
Output is correct |
103 |
Correct |
381 ms |
11768 KB |
Output is correct |
104 |
Correct |
379 ms |
11512 KB |
Output is correct |
105 |
Correct |
379 ms |
11512 KB |
Output is correct |
106 |
Correct |
1082 ms |
334712 KB |
Output is correct |
107 |
Correct |
1121 ms |
309212 KB |
Output is correct |
108 |
Correct |
962 ms |
335736 KB |
Output is correct |
109 |
Correct |
1004 ms |
307448 KB |
Output is correct |
110 |
Correct |
962 ms |
336120 KB |
Output is correct |
111 |
Correct |
1033 ms |
307960 KB |
Output is correct |
112 |
Correct |
393 ms |
12792 KB |
Output is correct |
113 |
Correct |
401 ms |
12792 KB |
Output is correct |
114 |
Correct |
332 ms |
11768 KB |
Output is correct |
115 |
Correct |
330 ms |
11768 KB |
Output is correct |
116 |
Correct |
326 ms |
11384 KB |
Output is correct |
117 |
Correct |
332 ms |
11384 KB |
Output is correct |
118 |
Correct |
1122 ms |
413432 KB |
Output is correct |
119 |
Correct |
954 ms |
335224 KB |
Output is correct |
120 |
Correct |
1022 ms |
305536 KB |
Output is correct |
121 |
Correct |
1117 ms |
413408 KB |
Output is correct |
122 |
Correct |
946 ms |
333984 KB |
Output is correct |
123 |
Correct |
1022 ms |
308040 KB |
Output is correct |
124 |
Correct |
1099 ms |
413528 KB |
Output is correct |
125 |
Correct |
950 ms |
335328 KB |
Output is correct |
126 |
Correct |
1006 ms |
307320 KB |
Output is correct |