#include <cstdio>
#include <iostream>
#include <algorithm>
#include <string>
#include <cstring>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <cmath>
#include <iomanip>
#include <cassert>
#include <bitset>
using namespace std;
typedef pair<int, int> P;
#define rep(i, n) for (int i=0; i<(n); i++)
#define all(c) (c).begin(), (c).end()
#define uniq(c) c.erase(unique(all(c)), (c).end())
#define index(xs, x) (int)(lower_bound(all(xs), x) - xs.begin())
#define _1 first
#define _2 second
#define pb push_back
#define INF 1145141919
#define MOD 1000000007
const int B = 100;
int N, M, Q;
vector<int> G[100000], Grev[100000];
int D[100000];
bool BAD[100000];
vector<P> dp[100000];
bool used[100000];
vector<P> filter(const vector<P> &seq) {
vector<P> ret;
for (P p : seq) if (!used[p._2]) ret.pb(p), used[p._2] = true;
for (P p : seq) used[p._2] = false;
if (ret.size() > B) ret.resize(B);
return ret;
}
vector<P> merge(const vector<P> &a, const vector<P> &b) {
vector<P> ret;
int x = 0, y = 0;
while (x<a.size() && y<b.size()) {
if (a[x]>=b[y]) ret.pb(a[x++]);
else ret.pb(b[y++]);
}
while (x<a.size()) ret.pb(a[x++]);
while (y<b.size()) ret.pb(b[y++]);
return filter(ret);
}
int solve(int s) {
rep(i, N) D[i] = -1;
D[s] = 0;
int m = -1;
for (int x=s; x>=0; x--) if (D[x] != -1) {
if (!BAD[x]) m = max(m, D[x]);
for (int t : Grev[x]) D[t] = max(D[t], D[x]+1);
}
return m;
}
signed main() {
ios::sync_with_stdio(false); cin.tie(0);
cin >> N >> M >> Q;
rep(i, M) {
int a, b;
cin >> a >> b;
a--, b--;
G[a].pb(b);
Grev[b].pb(a);
}
rep(x, N) dp[x].pb(P(0, x));
rep(x, N) {
vector<P> seq(dp[x]);
for (P &p : seq) p._1++;
for (int t : G[x]) dp[t] = merge(dp[t], seq);
}
rep(i, Q) {
int x, k;
cin >> x >> k;
x--;
vector<int> bad(k);
rep(i, k) cin >> bad[i], bad[i]--;
for (int i : bad) BAD[i] = true;
if (k < B) {
int m = -1;
for (P p : dp[x]) if (!BAD[p._2]) m = max(m, p._1);
cout << m << "\n";
}
else {
cout << solve(x) << "\n";
}
for (int i : bad) BAD[i] = false;
}
return 0;
}
Compilation message
bitaro.cpp: In function 'std::vector<std::pair<int, int> > merge(const std::vector<std::pair<int, int> >&, const std::vector<std::pair<int, int> >&)':
bitaro.cpp:46:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (x<a.size() && y<b.size()) {
~^~~~~~~~~
bitaro.cpp:46:25: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (x<a.size() && y<b.size()) {
~^~~~~~~~~
bitaro.cpp:50:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (x<a.size()) ret.pb(a[x++]);
~^~~~~~~~~
bitaro.cpp:51:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
while (y<b.size()) ret.pb(b[y++]);
~^~~~~~~~~
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7416 KB |
Output is correct |
2 |
Correct |
10 ms |
7416 KB |
Output is correct |
3 |
Correct |
10 ms |
7436 KB |
Output is correct |
4 |
Correct |
9 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
8096 KB |
Output is correct |
6 |
Correct |
14 ms |
8140 KB |
Output is correct |
7 |
Correct |
14 ms |
8140 KB |
Output is correct |
8 |
Correct |
16 ms |
8652 KB |
Output is correct |
9 |
Correct |
18 ms |
8652 KB |
Output is correct |
10 |
Correct |
16 ms |
8652 KB |
Output is correct |
11 |
Correct |
16 ms |
8652 KB |
Output is correct |
12 |
Correct |
15 ms |
8652 KB |
Output is correct |
13 |
Correct |
16 ms |
8684 KB |
Output is correct |
14 |
Correct |
15 ms |
8684 KB |
Output is correct |
15 |
Correct |
16 ms |
8684 KB |
Output is correct |
16 |
Correct |
13 ms |
8684 KB |
Output is correct |
17 |
Correct |
16 ms |
8684 KB |
Output is correct |
18 |
Correct |
17 ms |
8684 KB |
Output is correct |
19 |
Correct |
15 ms |
8684 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7416 KB |
Output is correct |
2 |
Correct |
10 ms |
7416 KB |
Output is correct |
3 |
Correct |
10 ms |
7436 KB |
Output is correct |
4 |
Correct |
9 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
8096 KB |
Output is correct |
6 |
Correct |
14 ms |
8140 KB |
Output is correct |
7 |
Correct |
14 ms |
8140 KB |
Output is correct |
8 |
Correct |
16 ms |
8652 KB |
Output is correct |
9 |
Correct |
18 ms |
8652 KB |
Output is correct |
10 |
Correct |
16 ms |
8652 KB |
Output is correct |
11 |
Correct |
16 ms |
8652 KB |
Output is correct |
12 |
Correct |
15 ms |
8652 KB |
Output is correct |
13 |
Correct |
16 ms |
8684 KB |
Output is correct |
14 |
Correct |
15 ms |
8684 KB |
Output is correct |
15 |
Correct |
16 ms |
8684 KB |
Output is correct |
16 |
Correct |
13 ms |
8684 KB |
Output is correct |
17 |
Correct |
16 ms |
8684 KB |
Output is correct |
18 |
Correct |
17 ms |
8684 KB |
Output is correct |
19 |
Correct |
15 ms |
8684 KB |
Output is correct |
20 |
Correct |
625 ms |
11008 KB |
Output is correct |
21 |
Correct |
586 ms |
11008 KB |
Output is correct |
22 |
Correct |
609 ms |
11100 KB |
Output is correct |
23 |
Correct |
599 ms |
11104 KB |
Output is correct |
24 |
Correct |
1144 ms |
116588 KB |
Output is correct |
25 |
Correct |
1285 ms |
116588 KB |
Output is correct |
26 |
Correct |
1314 ms |
116588 KB |
Output is correct |
27 |
Correct |
1103 ms |
116880 KB |
Output is correct |
28 |
Correct |
1089 ms |
116996 KB |
Output is correct |
29 |
Correct |
978 ms |
116996 KB |
Output is correct |
30 |
Correct |
958 ms |
116996 KB |
Output is correct |
31 |
Correct |
1196 ms |
137496 KB |
Output is correct |
32 |
Correct |
970 ms |
137496 KB |
Output is correct |
33 |
Correct |
830 ms |
137496 KB |
Output is correct |
34 |
Correct |
866 ms |
137496 KB |
Output is correct |
35 |
Correct |
780 ms |
137496 KB |
Output is correct |
36 |
Correct |
880 ms |
137496 KB |
Output is correct |
37 |
Correct |
997 ms |
137496 KB |
Output is correct |
38 |
Correct |
926 ms |
137496 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7416 KB |
Output is correct |
2 |
Correct |
10 ms |
7416 KB |
Output is correct |
3 |
Correct |
10 ms |
7436 KB |
Output is correct |
4 |
Correct |
9 ms |
7508 KB |
Output is correct |
5 |
Correct |
15 ms |
8096 KB |
Output is correct |
6 |
Correct |
14 ms |
8140 KB |
Output is correct |
7 |
Correct |
14 ms |
8140 KB |
Output is correct |
8 |
Correct |
16 ms |
8652 KB |
Output is correct |
9 |
Correct |
18 ms |
8652 KB |
Output is correct |
10 |
Correct |
16 ms |
8652 KB |
Output is correct |
11 |
Correct |
16 ms |
8652 KB |
Output is correct |
12 |
Correct |
15 ms |
8652 KB |
Output is correct |
13 |
Correct |
16 ms |
8684 KB |
Output is correct |
14 |
Correct |
15 ms |
8684 KB |
Output is correct |
15 |
Correct |
16 ms |
8684 KB |
Output is correct |
16 |
Correct |
13 ms |
8684 KB |
Output is correct |
17 |
Correct |
16 ms |
8684 KB |
Output is correct |
18 |
Correct |
17 ms |
8684 KB |
Output is correct |
19 |
Correct |
15 ms |
8684 KB |
Output is correct |
20 |
Correct |
625 ms |
11008 KB |
Output is correct |
21 |
Correct |
586 ms |
11008 KB |
Output is correct |
22 |
Correct |
609 ms |
11100 KB |
Output is correct |
23 |
Correct |
599 ms |
11104 KB |
Output is correct |
24 |
Correct |
1144 ms |
116588 KB |
Output is correct |
25 |
Correct |
1285 ms |
116588 KB |
Output is correct |
26 |
Correct |
1314 ms |
116588 KB |
Output is correct |
27 |
Correct |
1103 ms |
116880 KB |
Output is correct |
28 |
Correct |
1089 ms |
116996 KB |
Output is correct |
29 |
Correct |
978 ms |
116996 KB |
Output is correct |
30 |
Correct |
958 ms |
116996 KB |
Output is correct |
31 |
Correct |
1196 ms |
137496 KB |
Output is correct |
32 |
Correct |
970 ms |
137496 KB |
Output is correct |
33 |
Correct |
830 ms |
137496 KB |
Output is correct |
34 |
Correct |
866 ms |
137496 KB |
Output is correct |
35 |
Correct |
780 ms |
137496 KB |
Output is correct |
36 |
Correct |
880 ms |
137496 KB |
Output is correct |
37 |
Correct |
997 ms |
137496 KB |
Output is correct |
38 |
Correct |
926 ms |
137496 KB |
Output is correct |
39 |
Correct |
1211 ms |
137496 KB |
Output is correct |
40 |
Correct |
1159 ms |
137496 KB |
Output is correct |
41 |
Correct |
1224 ms |
137496 KB |
Output is correct |
42 |
Correct |
1088 ms |
137496 KB |
Output is correct |
43 |
Correct |
1195 ms |
137496 KB |
Output is correct |
44 |
Correct |
668 ms |
137496 KB |
Output is correct |
45 |
Correct |
639 ms |
137496 KB |
Output is correct |
46 |
Correct |
667 ms |
137496 KB |
Output is correct |
47 |
Correct |
618 ms |
137496 KB |
Output is correct |
48 |
Correct |
608 ms |
137496 KB |
Output is correct |
49 |
Correct |
1195 ms |
137496 KB |
Output is correct |
50 |
Correct |
1733 ms |
137496 KB |
Output is correct |
51 |
Correct |
667 ms |
137496 KB |
Output is correct |
52 |
Correct |
683 ms |
137496 KB |
Output is correct |
53 |
Correct |
1070 ms |
137496 KB |
Output is correct |
54 |
Correct |
1261 ms |
137496 KB |
Output is correct |
55 |
Correct |
1452 ms |
137496 KB |
Output is correct |
56 |
Correct |
1233 ms |
137496 KB |
Output is correct |
57 |
Correct |
661 ms |
137496 KB |
Output is correct |
58 |
Correct |
672 ms |
137496 KB |
Output is correct |
59 |
Correct |
692 ms |
137496 KB |
Output is correct |
60 |
Correct |
679 ms |
137496 KB |
Output is correct |
61 |
Correct |
1352 ms |
137496 KB |
Output is correct |
62 |
Correct |
1156 ms |
137496 KB |
Output is correct |
63 |
Correct |
1030 ms |
137496 KB |
Output is correct |
64 |
Correct |
1446 ms |
137496 KB |
Output is correct |
65 |
Correct |
1089 ms |
137496 KB |
Output is correct |
66 |
Correct |
1177 ms |
137496 KB |
Output is correct |
67 |
Correct |
1608 ms |
137496 KB |
Output is correct |
68 |
Correct |
1275 ms |
137496 KB |
Output is correct |
69 |
Correct |
1343 ms |
137496 KB |
Output is correct |
70 |
Correct |
1199 ms |
137496 KB |
Output is correct |
71 |
Correct |
1062 ms |
137496 KB |
Output is correct |
72 |
Correct |
1203 ms |
137496 KB |
Output is correct |
73 |
Correct |
1094 ms |
137496 KB |
Output is correct |
74 |
Correct |
953 ms |
137496 KB |
Output is correct |
75 |
Correct |
1014 ms |
137496 KB |
Output is correct |
76 |
Correct |
1309 ms |
137496 KB |
Output is correct |
77 |
Execution timed out |
2033 ms |
137496 KB |
Time limit exceeded |
78 |
Halted |
0 ms |
0 KB |
- |