#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 = 250;
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(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(vector<P> a, 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(std::vector<std::pair<int, int> >, 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 |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
8 ms |
7504 KB |
Output is correct |
5 |
Correct |
11 ms |
8220 KB |
Output is correct |
6 |
Correct |
14 ms |
8268 KB |
Output is correct |
7 |
Correct |
14 ms |
8268 KB |
Output is correct |
8 |
Correct |
23 ms |
9808 KB |
Output is correct |
9 |
Correct |
23 ms |
9836 KB |
Output is correct |
10 |
Correct |
24 ms |
9836 KB |
Output is correct |
11 |
Correct |
23 ms |
9836 KB |
Output is correct |
12 |
Correct |
18 ms |
9836 KB |
Output is correct |
13 |
Correct |
25 ms |
9840 KB |
Output is correct |
14 |
Correct |
20 ms |
9840 KB |
Output is correct |
15 |
Correct |
18 ms |
9840 KB |
Output is correct |
16 |
Correct |
19 ms |
9840 KB |
Output is correct |
17 |
Correct |
20 ms |
9840 KB |
Output is correct |
18 |
Correct |
17 ms |
9840 KB |
Output is correct |
19 |
Correct |
20 ms |
9840 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
8 ms |
7504 KB |
Output is correct |
5 |
Correct |
11 ms |
8220 KB |
Output is correct |
6 |
Correct |
14 ms |
8268 KB |
Output is correct |
7 |
Correct |
14 ms |
8268 KB |
Output is correct |
8 |
Correct |
23 ms |
9808 KB |
Output is correct |
9 |
Correct |
23 ms |
9836 KB |
Output is correct |
10 |
Correct |
24 ms |
9836 KB |
Output is correct |
11 |
Correct |
23 ms |
9836 KB |
Output is correct |
12 |
Correct |
18 ms |
9836 KB |
Output is correct |
13 |
Correct |
25 ms |
9840 KB |
Output is correct |
14 |
Correct |
20 ms |
9840 KB |
Output is correct |
15 |
Correct |
18 ms |
9840 KB |
Output is correct |
16 |
Correct |
19 ms |
9840 KB |
Output is correct |
17 |
Correct |
20 ms |
9840 KB |
Output is correct |
18 |
Correct |
17 ms |
9840 KB |
Output is correct |
19 |
Correct |
20 ms |
9840 KB |
Output is correct |
20 |
Correct |
1112 ms |
12056 KB |
Output is correct |
21 |
Correct |
1038 ms |
12304 KB |
Output is correct |
22 |
Correct |
1071 ms |
12304 KB |
Output is correct |
23 |
Correct |
1224 ms |
12304 KB |
Output is correct |
24 |
Correct |
1931 ms |
239508 KB |
Output is correct |
25 |
Execution timed out |
2021 ms |
247460 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
10 ms |
7416 KB |
Output is correct |
2 |
Correct |
9 ms |
7416 KB |
Output is correct |
3 |
Correct |
9 ms |
7488 KB |
Output is correct |
4 |
Correct |
8 ms |
7504 KB |
Output is correct |
5 |
Correct |
11 ms |
8220 KB |
Output is correct |
6 |
Correct |
14 ms |
8268 KB |
Output is correct |
7 |
Correct |
14 ms |
8268 KB |
Output is correct |
8 |
Correct |
23 ms |
9808 KB |
Output is correct |
9 |
Correct |
23 ms |
9836 KB |
Output is correct |
10 |
Correct |
24 ms |
9836 KB |
Output is correct |
11 |
Correct |
23 ms |
9836 KB |
Output is correct |
12 |
Correct |
18 ms |
9836 KB |
Output is correct |
13 |
Correct |
25 ms |
9840 KB |
Output is correct |
14 |
Correct |
20 ms |
9840 KB |
Output is correct |
15 |
Correct |
18 ms |
9840 KB |
Output is correct |
16 |
Correct |
19 ms |
9840 KB |
Output is correct |
17 |
Correct |
20 ms |
9840 KB |
Output is correct |
18 |
Correct |
17 ms |
9840 KB |
Output is correct |
19 |
Correct |
20 ms |
9840 KB |
Output is correct |
20 |
Correct |
1112 ms |
12056 KB |
Output is correct |
21 |
Correct |
1038 ms |
12304 KB |
Output is correct |
22 |
Correct |
1071 ms |
12304 KB |
Output is correct |
23 |
Correct |
1224 ms |
12304 KB |
Output is correct |
24 |
Correct |
1931 ms |
239508 KB |
Output is correct |
25 |
Execution timed out |
2021 ms |
247460 KB |
Time limit exceeded |
26 |
Halted |
0 ms |
0 KB |
- |