#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1e5;
const int BLOCK = 320;
int N, M, Q;
vector<int> to[MAXN + 10];
struct dat {
int w, u;
dat(int w_, int u_) : w(w_), u(u_) {}
dat(const dat& d) : w(d.w), u(d.u) {}
// datA before datB if datA.w > datB.w
bool operator<(dat d) const {
if(w == d.w) return u < d.u;
return w > d.w;
}
};
vector<int> from[MAXN + 10];
int qi = 0;
int bad[MAXN + 10];
int dp[MAXN + 10];
int solve1(int V) {
for(int v = 1; v <= V; v++) {
if(bad[v] != qi) dp[v] = 0;
else dp[v] = -1e9;
for(int u : from[v]) {
dp[v] = max(dp[v], 1 + dp[u]);
}
}
if(dp[V] < 0) dp[V] = -1;
return dp[V];
}
vector<dat> best[MAXN + 10];
int done[MAXN + 10], di = 0;
void work(int u) {
vector<dat> cp(best[u].begin(), best[u].end());
for(dat& it : cp) it.w++;
for(int v : to[u]) {
auto mIt = best[v].insert(best[v].end(), cp.begin(), cp.end());
inplace_merge(best[v].begin(), mIt, best[v].end());
vector<dat> cpV; cpV.reserve(BLOCK);
++di;
for(auto it : best[v]) {
if(done[it.u] < di) {
done[it.u] = di;
cpV.push_back(it);
}
if(cpV.size() >= BLOCK) break;
}
best[v].swap(cpV);
}
}
int solve2(int V) {
for(auto& it : best[V]) {
if(bad[it.u] != qi) return it.w;
}
if(bad[V] != qi) return 0;
return -1;
}
int main() {
assert(scanf("%d%d%d", &N, &M, &Q) == 3);
for(int i = 0; i < M; i++) {
int u, v; assert(scanf("%d%d", &u, &v) == 2);
to[u].push_back(v);
from[v].push_back(u);
}
for(int u = 1; u <= N; u++) {
best[u].emplace_back(0, u);
}
for(int u = 1; u <= N; u++) {
work(u);
}
for(qi = 1; qi <= Q; qi++) {
int dest, badc;
assert(scanf("%d%d", &dest, &badc) == 2);
for(int i = 0; i < badc; i++) {
int v; assert(scanf("%d", &v) == 1);
bad[v] = qi;
}
int res = -1;
if(badc >= BLOCK) res = solve1(dest);
else res = solve2(dest);
printf("%d\n", res);
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7288 KB |
Output is correct |
2 |
Correct |
9 ms |
7412 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
10 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
9760 KB |
Output is correct |
6 |
Correct |
16 ms |
9888 KB |
Output is correct |
7 |
Correct |
15 ms |
9888 KB |
Output is correct |
8 |
Correct |
24 ms |
10144 KB |
Output is correct |
9 |
Correct |
21 ms |
10144 KB |
Output is correct |
10 |
Correct |
21 ms |
10144 KB |
Output is correct |
11 |
Correct |
20 ms |
10144 KB |
Output is correct |
12 |
Correct |
17 ms |
10212 KB |
Output is correct |
13 |
Correct |
22 ms |
10212 KB |
Output is correct |
14 |
Correct |
19 ms |
10212 KB |
Output is correct |
15 |
Correct |
17 ms |
10212 KB |
Output is correct |
16 |
Correct |
18 ms |
10212 KB |
Output is correct |
17 |
Correct |
17 ms |
10212 KB |
Output is correct |
18 |
Correct |
15 ms |
10212 KB |
Output is correct |
19 |
Correct |
17 ms |
10212 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7288 KB |
Output is correct |
2 |
Correct |
9 ms |
7412 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
10 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
9760 KB |
Output is correct |
6 |
Correct |
16 ms |
9888 KB |
Output is correct |
7 |
Correct |
15 ms |
9888 KB |
Output is correct |
8 |
Correct |
24 ms |
10144 KB |
Output is correct |
9 |
Correct |
21 ms |
10144 KB |
Output is correct |
10 |
Correct |
21 ms |
10144 KB |
Output is correct |
11 |
Correct |
20 ms |
10144 KB |
Output is correct |
12 |
Correct |
17 ms |
10212 KB |
Output is correct |
13 |
Correct |
22 ms |
10212 KB |
Output is correct |
14 |
Correct |
19 ms |
10212 KB |
Output is correct |
15 |
Correct |
17 ms |
10212 KB |
Output is correct |
16 |
Correct |
18 ms |
10212 KB |
Output is correct |
17 |
Correct |
17 ms |
10212 KB |
Output is correct |
18 |
Correct |
15 ms |
10212 KB |
Output is correct |
19 |
Correct |
17 ms |
10212 KB |
Output is correct |
20 |
Correct |
773 ms |
12584 KB |
Output is correct |
21 |
Correct |
736 ms |
12656 KB |
Output is correct |
22 |
Correct |
755 ms |
12784 KB |
Output is correct |
23 |
Correct |
909 ms |
12784 KB |
Output is correct |
24 |
Correct |
1310 ms |
235148 KB |
Output is correct |
25 |
Correct |
1460 ms |
235148 KB |
Output is correct |
26 |
Correct |
1406 ms |
235148 KB |
Output is correct |
27 |
Correct |
1423 ms |
267712 KB |
Output is correct |
28 |
Correct |
1290 ms |
270296 KB |
Output is correct |
29 |
Correct |
1287 ms |
270724 KB |
Output is correct |
30 |
Correct |
1523 ms |
270724 KB |
Output is correct |
31 |
Correct |
1514 ms |
270724 KB |
Output is correct |
32 |
Correct |
1426 ms |
270724 KB |
Output is correct |
33 |
Correct |
1185 ms |
270724 KB |
Output is correct |
34 |
Correct |
1098 ms |
270724 KB |
Output is correct |
35 |
Correct |
1175 ms |
270724 KB |
Output is correct |
36 |
Correct |
1207 ms |
270724 KB |
Output is correct |
37 |
Correct |
1285 ms |
270724 KB |
Output is correct |
38 |
Correct |
1169 ms |
270724 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
9 ms |
7288 KB |
Output is correct |
2 |
Correct |
9 ms |
7412 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
10 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
9760 KB |
Output is correct |
6 |
Correct |
16 ms |
9888 KB |
Output is correct |
7 |
Correct |
15 ms |
9888 KB |
Output is correct |
8 |
Correct |
24 ms |
10144 KB |
Output is correct |
9 |
Correct |
21 ms |
10144 KB |
Output is correct |
10 |
Correct |
21 ms |
10144 KB |
Output is correct |
11 |
Correct |
20 ms |
10144 KB |
Output is correct |
12 |
Correct |
17 ms |
10212 KB |
Output is correct |
13 |
Correct |
22 ms |
10212 KB |
Output is correct |
14 |
Correct |
19 ms |
10212 KB |
Output is correct |
15 |
Correct |
17 ms |
10212 KB |
Output is correct |
16 |
Correct |
18 ms |
10212 KB |
Output is correct |
17 |
Correct |
17 ms |
10212 KB |
Output is correct |
18 |
Correct |
15 ms |
10212 KB |
Output is correct |
19 |
Correct |
17 ms |
10212 KB |
Output is correct |
20 |
Correct |
773 ms |
12584 KB |
Output is correct |
21 |
Correct |
736 ms |
12656 KB |
Output is correct |
22 |
Correct |
755 ms |
12784 KB |
Output is correct |
23 |
Correct |
909 ms |
12784 KB |
Output is correct |
24 |
Correct |
1310 ms |
235148 KB |
Output is correct |
25 |
Correct |
1460 ms |
235148 KB |
Output is correct |
26 |
Correct |
1406 ms |
235148 KB |
Output is correct |
27 |
Correct |
1423 ms |
267712 KB |
Output is correct |
28 |
Correct |
1290 ms |
270296 KB |
Output is correct |
29 |
Correct |
1287 ms |
270724 KB |
Output is correct |
30 |
Correct |
1523 ms |
270724 KB |
Output is correct |
31 |
Correct |
1514 ms |
270724 KB |
Output is correct |
32 |
Correct |
1426 ms |
270724 KB |
Output is correct |
33 |
Correct |
1185 ms |
270724 KB |
Output is correct |
34 |
Correct |
1098 ms |
270724 KB |
Output is correct |
35 |
Correct |
1175 ms |
270724 KB |
Output is correct |
36 |
Correct |
1207 ms |
270724 KB |
Output is correct |
37 |
Correct |
1285 ms |
270724 KB |
Output is correct |
38 |
Correct |
1169 ms |
270724 KB |
Output is correct |
39 |
Correct |
1697 ms |
270724 KB |
Output is correct |
40 |
Correct |
1440 ms |
270724 KB |
Output is correct |
41 |
Correct |
1488 ms |
270724 KB |
Output is correct |
42 |
Correct |
1609 ms |
270724 KB |
Output is correct |
43 |
Correct |
1575 ms |
270724 KB |
Output is correct |
44 |
Correct |
836 ms |
270724 KB |
Output is correct |
45 |
Correct |
772 ms |
270724 KB |
Output is correct |
46 |
Correct |
827 ms |
270724 KB |
Output is correct |
47 |
Correct |
777 ms |
270724 KB |
Output is correct |
48 |
Correct |
785 ms |
270724 KB |
Output is correct |
49 |
Correct |
1521 ms |
270928 KB |
Output is correct |
50 |
Correct |
1354 ms |
270928 KB |
Output is correct |
51 |
Correct |
776 ms |
270928 KB |
Output is correct |
52 |
Correct |
730 ms |
270928 KB |
Output is correct |
53 |
Correct |
1245 ms |
270928 KB |
Output is correct |
54 |
Correct |
1343 ms |
270928 KB |
Output is correct |
55 |
Correct |
1231 ms |
270928 KB |
Output is correct |
56 |
Correct |
1228 ms |
270928 KB |
Output is correct |
57 |
Correct |
799 ms |
270928 KB |
Output is correct |
58 |
Correct |
790 ms |
270928 KB |
Output is correct |
59 |
Correct |
767 ms |
270928 KB |
Output is correct |
60 |
Correct |
817 ms |
270928 KB |
Output is correct |
61 |
Correct |
1461 ms |
270928 KB |
Output is correct |
62 |
Correct |
1433 ms |
270928 KB |
Output is correct |
63 |
Correct |
1577 ms |
270928 KB |
Output is correct |
64 |
Correct |
1927 ms |
270928 KB |
Output is correct |
65 |
Correct |
1698 ms |
270928 KB |
Output is correct |
66 |
Correct |
1746 ms |
270928 KB |
Output is correct |
67 |
Correct |
1449 ms |
277884 KB |
Output is correct |
68 |
Correct |
1320 ms |
277884 KB |
Output is correct |
69 |
Correct |
1280 ms |
277884 KB |
Output is correct |
70 |
Correct |
1449 ms |
286232 KB |
Output is correct |
71 |
Correct |
1288 ms |
286232 KB |
Output is correct |
72 |
Correct |
1396 ms |
286232 KB |
Output is correct |
73 |
Correct |
1474 ms |
294164 KB |
Output is correct |
74 |
Correct |
1348 ms |
294164 KB |
Output is correct |
75 |
Correct |
1420 ms |
294164 KB |
Output is correct |
76 |
Correct |
1483 ms |
300920 KB |
Output is correct |
77 |
Correct |
1365 ms |
300920 KB |
Output is correct |
78 |
Correct |
1362 ms |
300920 KB |
Output is correct |
79 |
Correct |
782 ms |
300920 KB |
Output is correct |
80 |
Correct |
735 ms |
300920 KB |
Output is correct |
81 |
Correct |
772 ms |
300920 KB |
Output is correct |
82 |
Correct |
1664 ms |
300920 KB |
Output is correct |
83 |
Correct |
1648 ms |
300920 KB |
Output is correct |
84 |
Correct |
1471 ms |
300920 KB |
Output is correct |
85 |
Correct |
1423 ms |
300920 KB |
Output is correct |
86 |
Correct |
1527 ms |
300920 KB |
Output is correct |
87 |
Correct |
1501 ms |
300920 KB |
Output is correct |
88 |
Correct |
780 ms |
300920 KB |
Output is correct |
89 |
Correct |
811 ms |
300920 KB |
Output is correct |
90 |
Correct |
762 ms |
300920 KB |
Output is correct |
91 |
Correct |
746 ms |
300920 KB |
Output is correct |
92 |
Correct |
763 ms |
300920 KB |
Output is correct |
93 |
Correct |
757 ms |
300920 KB |
Output is correct |
94 |
Correct |
1143 ms |
300920 KB |
Output is correct |
95 |
Correct |
1186 ms |
300920 KB |
Output is correct |
96 |
Correct |
1198 ms |
300920 KB |
Output is correct |
97 |
Correct |
1205 ms |
300920 KB |
Output is correct |
98 |
Correct |
1373 ms |
300920 KB |
Output is correct |
99 |
Correct |
1243 ms |
300920 KB |
Output is correct |
100 |
Correct |
989 ms |
300920 KB |
Output is correct |
101 |
Correct |
942 ms |
300920 KB |
Output is correct |
102 |
Correct |
962 ms |
300920 KB |
Output is correct |
103 |
Correct |
972 ms |
300920 KB |
Output is correct |
104 |
Correct |
976 ms |
300920 KB |
Output is correct |
105 |
Correct |
953 ms |
300920 KB |
Output is correct |
106 |
Correct |
1390 ms |
300920 KB |
Output is correct |
107 |
Correct |
1389 ms |
300920 KB |
Output is correct |
108 |
Correct |
1229 ms |
300920 KB |
Output is correct |
109 |
Correct |
1195 ms |
300920 KB |
Output is correct |
110 |
Correct |
1307 ms |
300920 KB |
Output is correct |
111 |
Correct |
1262 ms |
300920 KB |
Output is correct |
112 |
Correct |
856 ms |
300920 KB |
Output is correct |
113 |
Correct |
835 ms |
300920 KB |
Output is correct |
114 |
Correct |
809 ms |
300920 KB |
Output is correct |
115 |
Correct |
787 ms |
300920 KB |
Output is correct |
116 |
Correct |
819 ms |
300920 KB |
Output is correct |
117 |
Correct |
822 ms |
300920 KB |
Output is correct |
118 |
Correct |
1399 ms |
300920 KB |
Output is correct |
119 |
Correct |
1247 ms |
300920 KB |
Output is correct |
120 |
Correct |
1242 ms |
300920 KB |
Output is correct |
121 |
Correct |
1386 ms |
300920 KB |
Output is correct |
122 |
Correct |
1316 ms |
300920 KB |
Output is correct |
123 |
Correct |
1310 ms |
300920 KB |
Output is correct |
124 |
Correct |
1318 ms |
300920 KB |
Output is correct |
125 |
Correct |
1230 ms |
300920 KB |
Output is correct |
126 |
Correct |
1212 ms |
300920 KB |
Output is correct |