#include <bits/stdc++.h>
using namespace std;
const int N = 1e5+1, INF = 1e9+1;
int n, m, q, bsz = 100;
vector<int> g[N];
vector<pair<int,int> > dp[N];
bool blocked[N];
int f[N];
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
cin >> n >> m >> q;
for(int i = 0, s, e; i < m; i++) {
cin >> s >> e;
--s, --e;
g[e].push_back(s);
}
dp[0].emplace_back(0, 0);
for(int i = 1; i < n; i++) {
dp[i].emplace_back(0, i);
for(int j: g[i]) for(auto x: dp[j]) dp[i].emplace_back(x.first + 1, x.second);
nth_element(dp[i].begin(), dp[i].begin() + min(bsz + 10, (int) dp[i].size()), dp[i].end(), greater<pair<int,int> >());
dp[i].resize(min(bsz + 10, (int) dp[i].size()));
}
while(q--) {
int targ, Y;
cin >> targ >> Y;
--targ;
vector<int> C(Y);
for(int i = 0; i < Y; i++) {
cin >> C[i];
--C[i];
blocked[C[i]] = true;
}
int res = -INF;
if(Y < bsz) {
for(auto p: dp[targ]) if(!blocked[p.second]) res = max(p.first, res);
} else {
fill(f, f+targ+1, 0);
for(int i: C) f[i] = -INF;
for(int i = 0; i <= targ; i++) {
for(int j: g[i]) f[i] = max(f[j] + 1, f[i]);
if(f[i] < 0) f[i] = -INF;
}
res = f[targ];
}
if(res == -INF) cout << -1;
else cout << res;
cout << '\n';
for(int i = 0; i < Y; i++) blocked[C[i]] = false;
}
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
7 ms |
5244 KB |
Output is correct |
4 |
Correct |
6 ms |
5244 KB |
Output is correct |
5 |
Correct |
13 ms |
6824 KB |
Output is correct |
6 |
Correct |
13 ms |
6824 KB |
Output is correct |
7 |
Correct |
13 ms |
6824 KB |
Output is correct |
8 |
Correct |
15 ms |
7532 KB |
Output is correct |
9 |
Correct |
15 ms |
7660 KB |
Output is correct |
10 |
Correct |
14 ms |
7660 KB |
Output is correct |
11 |
Correct |
14 ms |
7660 KB |
Output is correct |
12 |
Correct |
12 ms |
7660 KB |
Output is correct |
13 |
Correct |
16 ms |
7660 KB |
Output is correct |
14 |
Correct |
12 ms |
7660 KB |
Output is correct |
15 |
Correct |
12 ms |
7660 KB |
Output is correct |
16 |
Correct |
11 ms |
7660 KB |
Output is correct |
17 |
Correct |
14 ms |
7660 KB |
Output is correct |
18 |
Correct |
11 ms |
7660 KB |
Output is correct |
19 |
Correct |
13 ms |
7660 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
7 ms |
5244 KB |
Output is correct |
4 |
Correct |
6 ms |
5244 KB |
Output is correct |
5 |
Correct |
13 ms |
6824 KB |
Output is correct |
6 |
Correct |
13 ms |
6824 KB |
Output is correct |
7 |
Correct |
13 ms |
6824 KB |
Output is correct |
8 |
Correct |
15 ms |
7532 KB |
Output is correct |
9 |
Correct |
15 ms |
7660 KB |
Output is correct |
10 |
Correct |
14 ms |
7660 KB |
Output is correct |
11 |
Correct |
14 ms |
7660 KB |
Output is correct |
12 |
Correct |
12 ms |
7660 KB |
Output is correct |
13 |
Correct |
16 ms |
7660 KB |
Output is correct |
14 |
Correct |
12 ms |
7660 KB |
Output is correct |
15 |
Correct |
12 ms |
7660 KB |
Output is correct |
16 |
Correct |
11 ms |
7660 KB |
Output is correct |
17 |
Correct |
14 ms |
7660 KB |
Output is correct |
18 |
Correct |
11 ms |
7660 KB |
Output is correct |
19 |
Correct |
13 ms |
7660 KB |
Output is correct |
20 |
Correct |
433 ms |
178680 KB |
Output is correct |
21 |
Correct |
400 ms |
178828 KB |
Output is correct |
22 |
Correct |
422 ms |
178844 KB |
Output is correct |
23 |
Correct |
438 ms |
179572 KB |
Output is correct |
24 |
Correct |
845 ms |
193976 KB |
Output is correct |
25 |
Correct |
837 ms |
194984 KB |
Output is correct |
26 |
Correct |
875 ms |
195112 KB |
Output is correct |
27 |
Correct |
779 ms |
245000 KB |
Output is correct |
28 |
Correct |
772 ms |
245000 KB |
Output is correct |
29 |
Correct |
799 ms |
245000 KB |
Output is correct |
30 |
Correct |
852 ms |
245000 KB |
Output is correct |
31 |
Correct |
838 ms |
245000 KB |
Output is correct |
32 |
Correct |
810 ms |
245000 KB |
Output is correct |
33 |
Correct |
539 ms |
245000 KB |
Output is correct |
34 |
Correct |
552 ms |
245000 KB |
Output is correct |
35 |
Correct |
575 ms |
245000 KB |
Output is correct |
36 |
Correct |
711 ms |
245000 KB |
Output is correct |
37 |
Correct |
742 ms |
245000 KB |
Output is correct |
38 |
Correct |
736 ms |
245000 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
7 ms |
5244 KB |
Output is correct |
4 |
Correct |
6 ms |
5244 KB |
Output is correct |
5 |
Correct |
13 ms |
6824 KB |
Output is correct |
6 |
Correct |
13 ms |
6824 KB |
Output is correct |
7 |
Correct |
13 ms |
6824 KB |
Output is correct |
8 |
Correct |
15 ms |
7532 KB |
Output is correct |
9 |
Correct |
15 ms |
7660 KB |
Output is correct |
10 |
Correct |
14 ms |
7660 KB |
Output is correct |
11 |
Correct |
14 ms |
7660 KB |
Output is correct |
12 |
Correct |
12 ms |
7660 KB |
Output is correct |
13 |
Correct |
16 ms |
7660 KB |
Output is correct |
14 |
Correct |
12 ms |
7660 KB |
Output is correct |
15 |
Correct |
12 ms |
7660 KB |
Output is correct |
16 |
Correct |
11 ms |
7660 KB |
Output is correct |
17 |
Correct |
14 ms |
7660 KB |
Output is correct |
18 |
Correct |
11 ms |
7660 KB |
Output is correct |
19 |
Correct |
13 ms |
7660 KB |
Output is correct |
20 |
Correct |
433 ms |
178680 KB |
Output is correct |
21 |
Correct |
400 ms |
178828 KB |
Output is correct |
22 |
Correct |
422 ms |
178844 KB |
Output is correct |
23 |
Correct |
438 ms |
179572 KB |
Output is correct |
24 |
Correct |
845 ms |
193976 KB |
Output is correct |
25 |
Correct |
837 ms |
194984 KB |
Output is correct |
26 |
Correct |
875 ms |
195112 KB |
Output is correct |
27 |
Correct |
779 ms |
245000 KB |
Output is correct |
28 |
Correct |
772 ms |
245000 KB |
Output is correct |
29 |
Correct |
799 ms |
245000 KB |
Output is correct |
30 |
Correct |
852 ms |
245000 KB |
Output is correct |
31 |
Correct |
838 ms |
245000 KB |
Output is correct |
32 |
Correct |
810 ms |
245000 KB |
Output is correct |
33 |
Correct |
539 ms |
245000 KB |
Output is correct |
34 |
Correct |
552 ms |
245000 KB |
Output is correct |
35 |
Correct |
575 ms |
245000 KB |
Output is correct |
36 |
Correct |
711 ms |
245000 KB |
Output is correct |
37 |
Correct |
742 ms |
245000 KB |
Output is correct |
38 |
Correct |
736 ms |
245000 KB |
Output is correct |
39 |
Correct |
1045 ms |
245000 KB |
Output is correct |
40 |
Correct |
995 ms |
245000 KB |
Output is correct |
41 |
Correct |
1433 ms |
245000 KB |
Output is correct |
42 |
Correct |
1090 ms |
245000 KB |
Output is correct |
43 |
Correct |
949 ms |
245000 KB |
Output is correct |
44 |
Incorrect |
509 ms |
245000 KB |
Output isn't correct |
45 |
Halted |
0 ms |
0 KB |
- |