#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());
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;
}
}
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5132 KB |
Output is correct |
4 |
Correct |
6 ms |
5172 KB |
Output is correct |
5 |
Correct |
14 ms |
6784 KB |
Output is correct |
6 |
Correct |
13 ms |
6784 KB |
Output is correct |
7 |
Correct |
14 ms |
6784 KB |
Output is correct |
8 |
Correct |
16 ms |
7628 KB |
Output is correct |
9 |
Correct |
16 ms |
7628 KB |
Output is correct |
10 |
Correct |
16 ms |
7628 KB |
Output is correct |
11 |
Correct |
17 ms |
7628 KB |
Output is correct |
12 |
Correct |
15 ms |
7628 KB |
Output is correct |
13 |
Correct |
18 ms |
7628 KB |
Output is correct |
14 |
Correct |
13 ms |
7628 KB |
Output is correct |
15 |
Correct |
12 ms |
7628 KB |
Output is correct |
16 |
Correct |
13 ms |
7628 KB |
Output is correct |
17 |
Correct |
16 ms |
7628 KB |
Output is correct |
18 |
Correct |
12 ms |
7628 KB |
Output is correct |
19 |
Correct |
15 ms |
7628 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5132 KB |
Output is correct |
4 |
Correct |
6 ms |
5172 KB |
Output is correct |
5 |
Correct |
14 ms |
6784 KB |
Output is correct |
6 |
Correct |
13 ms |
6784 KB |
Output is correct |
7 |
Correct |
14 ms |
6784 KB |
Output is correct |
8 |
Correct |
16 ms |
7628 KB |
Output is correct |
9 |
Correct |
16 ms |
7628 KB |
Output is correct |
10 |
Correct |
16 ms |
7628 KB |
Output is correct |
11 |
Correct |
17 ms |
7628 KB |
Output is correct |
12 |
Correct |
15 ms |
7628 KB |
Output is correct |
13 |
Correct |
18 ms |
7628 KB |
Output is correct |
14 |
Correct |
13 ms |
7628 KB |
Output is correct |
15 |
Correct |
12 ms |
7628 KB |
Output is correct |
16 |
Correct |
13 ms |
7628 KB |
Output is correct |
17 |
Correct |
16 ms |
7628 KB |
Output is correct |
18 |
Correct |
12 ms |
7628 KB |
Output is correct |
19 |
Correct |
15 ms |
7628 KB |
Output is correct |
20 |
Correct |
633 ms |
178748 KB |
Output is correct |
21 |
Correct |
642 ms |
178876 KB |
Output is correct |
22 |
Correct |
571 ms |
178876 KB |
Output is correct |
23 |
Correct |
628 ms |
179340 KB |
Output is correct |
24 |
Correct |
1027 ms |
194044 KB |
Output is correct |
25 |
Correct |
962 ms |
194840 KB |
Output is correct |
26 |
Correct |
1072 ms |
195248 KB |
Output is correct |
27 |
Correct |
1046 ms |
245008 KB |
Output is correct |
28 |
Correct |
999 ms |
245008 KB |
Output is correct |
29 |
Correct |
1020 ms |
245008 KB |
Output is correct |
30 |
Correct |
1100 ms |
245008 KB |
Output is correct |
31 |
Correct |
1031 ms |
245008 KB |
Output is correct |
32 |
Correct |
1089 ms |
245008 KB |
Output is correct |
33 |
Correct |
639 ms |
245008 KB |
Output is correct |
34 |
Correct |
622 ms |
245008 KB |
Output is correct |
35 |
Correct |
689 ms |
245008 KB |
Output is correct |
36 |
Correct |
874 ms |
245008 KB |
Output is correct |
37 |
Correct |
807 ms |
245008 KB |
Output is correct |
38 |
Correct |
863 ms |
245008 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
6 ms |
4984 KB |
Output is correct |
2 |
Correct |
6 ms |
5108 KB |
Output is correct |
3 |
Correct |
6 ms |
5132 KB |
Output is correct |
4 |
Correct |
6 ms |
5172 KB |
Output is correct |
5 |
Correct |
14 ms |
6784 KB |
Output is correct |
6 |
Correct |
13 ms |
6784 KB |
Output is correct |
7 |
Correct |
14 ms |
6784 KB |
Output is correct |
8 |
Correct |
16 ms |
7628 KB |
Output is correct |
9 |
Correct |
16 ms |
7628 KB |
Output is correct |
10 |
Correct |
16 ms |
7628 KB |
Output is correct |
11 |
Correct |
17 ms |
7628 KB |
Output is correct |
12 |
Correct |
15 ms |
7628 KB |
Output is correct |
13 |
Correct |
18 ms |
7628 KB |
Output is correct |
14 |
Correct |
13 ms |
7628 KB |
Output is correct |
15 |
Correct |
12 ms |
7628 KB |
Output is correct |
16 |
Correct |
13 ms |
7628 KB |
Output is correct |
17 |
Correct |
16 ms |
7628 KB |
Output is correct |
18 |
Correct |
12 ms |
7628 KB |
Output is correct |
19 |
Correct |
15 ms |
7628 KB |
Output is correct |
20 |
Correct |
633 ms |
178748 KB |
Output is correct |
21 |
Correct |
642 ms |
178876 KB |
Output is correct |
22 |
Correct |
571 ms |
178876 KB |
Output is correct |
23 |
Correct |
628 ms |
179340 KB |
Output is correct |
24 |
Correct |
1027 ms |
194044 KB |
Output is correct |
25 |
Correct |
962 ms |
194840 KB |
Output is correct |
26 |
Correct |
1072 ms |
195248 KB |
Output is correct |
27 |
Correct |
1046 ms |
245008 KB |
Output is correct |
28 |
Correct |
999 ms |
245008 KB |
Output is correct |
29 |
Correct |
1020 ms |
245008 KB |
Output is correct |
30 |
Correct |
1100 ms |
245008 KB |
Output is correct |
31 |
Correct |
1031 ms |
245008 KB |
Output is correct |
32 |
Correct |
1089 ms |
245008 KB |
Output is correct |
33 |
Correct |
639 ms |
245008 KB |
Output is correct |
34 |
Correct |
622 ms |
245008 KB |
Output is correct |
35 |
Correct |
689 ms |
245008 KB |
Output is correct |
36 |
Correct |
874 ms |
245008 KB |
Output is correct |
37 |
Correct |
807 ms |
245008 KB |
Output is correct |
38 |
Correct |
863 ms |
245008 KB |
Output is correct |
39 |
Incorrect |
1123 ms |
245008 KB |
Output isn't correct |
40 |
Halted |
0 ms |
0 KB |
- |