/**
* code generated by JHelper
* More info: https://github.com/AlexeyDmitriev/JHelper
* @author
*/
#include <bits/stdc++.h>
using namespace std;
#define long long long
const long MOD = 1e9+7, LINF = 1e18 + 1e16;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
const int MAGIC = 2, N = 1e5+1;
class Bitaro {
int n, m, q, indeg[N];
vector<int> adj[N];
pair<int,int> dp[N][MAGIC], dp2[N];
bool blocked[N];
void naive() {
fill(dp2, dp2+n+1, make_pair(-INF, -1));
for(int u = 1; u <= n; u++) {
if(!blocked[u]) dp2[u] = {0, u};
for(int v: adj[u]) if(dp2[v].first + 1 > dp2[u].first) {
dp2[u] = {dp2[v].first + 1, dp2[v].second};
}
}
}
void preprocess() {
for(int i = 1; i <= n; i++) for(int j = 0; j < MAGIC; j++) dp[i][j] = {-INF, -1};
for(int u = 1; u <= n; u++) {
dp[u][0] = {0, u};
for(int v: adj[u]) {
pair<int,int> tmp[2*MAGIC];
int i = 0, j = 0, idx = 0;
while(idx < 2*MAGIC) {
if(j == MAGIC || dp[u][i].first > dp[v][j].first + 1) tmp[idx++] = dp[u][i++];
else {
tmp[idx++] = make_pair(dp[v][j].first + 1, dp[v][j].second);
++j;
}
}
unique(tmp, tmp+2*MAGIC, [] (auto p1, auto p2) { return p1.second == p2.second; });
copy(tmp, tmp+MAGIC, dp[u]);
}
// cout << "dp[u] " << u << endl;
// for(int i = 0; i < MAGIC; i++) cout << dp[u][i].first << ' ' << dp[u][i].second << endl;
// cout << endl;
}
}
public:
void solve(istream &cin, ostream &cout) {
cin >> n >> m >> q;
for(int i = 0, s, e; i < m; i++) {
cin >> s >> e;
adj[e].push_back(s);
// ++indeg[e];
}
preprocess();
for(int i = 0, T, Y; i < q; i++) {
cin >> T >> Y;
vector<int> ls(Y);
for(int j = 0, v; j < Y; j++) {
cin >> ls[j];
blocked[ls[j]] = true;
}
if(Y >= MAGIC) {
naive();
cout << (dp2[T].first < 0 ? -1 : dp2[T].first) << '\n';
} else {
bool found = false;
for(int i = 0; i < MAGIC; i++) if(dp[T][i].second != -1 && !blocked[dp[T][i].second]) {
cout << dp[T][i].first << '\n';
found = true;
break;
}
if(!found) cout << -1 << '\n';
}
for(int v: ls) blocked[v] = false;
}
}
};
class Solver {
public:
void solve(std::istream& in, std::ostream& out) {
Bitaro *obj = new Bitaro();
obj->solve(in, out);
delete obj;
}
};
int main() {
ios::sync_with_stdio(false);
cin.tie(0);
Solver solver;
std::istream& in(std::cin);
std::ostream& out(std::cout);
solver.solve(in, out);
return 0;
}
Compilation message
bitaro.cpp: In member function 'void Bitaro::solve(std::istream&, std::ostream&)':
bitaro.cpp:67:19: warning: unused variable 'v' [-Wunused-variable]
for(int j = 0, v; j < Y; j++) {
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5624 KB |
Output is correct |
2 |
Correct |
5 ms |
5496 KB |
Output is correct |
3 |
Correct |
5 ms |
5496 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
7 ms |
5500 KB |
Output is correct |
6 |
Correct |
6 ms |
5624 KB |
Output is correct |
7 |
Correct |
6 ms |
5496 KB |
Output is correct |
8 |
Correct |
6 ms |
5496 KB |
Output is correct |
9 |
Correct |
6 ms |
5624 KB |
Output is correct |
10 |
Correct |
6 ms |
5496 KB |
Output is correct |
11 |
Correct |
6 ms |
5496 KB |
Output is correct |
12 |
Correct |
6 ms |
5496 KB |
Output is correct |
13 |
Correct |
6 ms |
5624 KB |
Output is correct |
14 |
Correct |
6 ms |
5628 KB |
Output is correct |
15 |
Correct |
6 ms |
5624 KB |
Output is correct |
16 |
Correct |
7 ms |
5496 KB |
Output is correct |
17 |
Correct |
6 ms |
5496 KB |
Output is correct |
18 |
Correct |
6 ms |
5624 KB |
Output is correct |
19 |
Correct |
6 ms |
5624 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5624 KB |
Output is correct |
2 |
Correct |
5 ms |
5496 KB |
Output is correct |
3 |
Correct |
5 ms |
5496 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
7 ms |
5500 KB |
Output is correct |
6 |
Correct |
6 ms |
5624 KB |
Output is correct |
7 |
Correct |
6 ms |
5496 KB |
Output is correct |
8 |
Correct |
6 ms |
5496 KB |
Output is correct |
9 |
Correct |
6 ms |
5624 KB |
Output is correct |
10 |
Correct |
6 ms |
5496 KB |
Output is correct |
11 |
Correct |
6 ms |
5496 KB |
Output is correct |
12 |
Correct |
6 ms |
5496 KB |
Output is correct |
13 |
Correct |
6 ms |
5624 KB |
Output is correct |
14 |
Correct |
6 ms |
5628 KB |
Output is correct |
15 |
Correct |
6 ms |
5624 KB |
Output is correct |
16 |
Correct |
7 ms |
5496 KB |
Output is correct |
17 |
Correct |
6 ms |
5496 KB |
Output is correct |
18 |
Correct |
6 ms |
5624 KB |
Output is correct |
19 |
Correct |
6 ms |
5624 KB |
Output is correct |
20 |
Correct |
39 ms |
7672 KB |
Output is correct |
21 |
Correct |
39 ms |
7672 KB |
Output is correct |
22 |
Correct |
39 ms |
7672 KB |
Output is correct |
23 |
Correct |
39 ms |
7672 KB |
Output is correct |
24 |
Correct |
94 ms |
9564 KB |
Output is correct |
25 |
Correct |
98 ms |
9976 KB |
Output is correct |
26 |
Correct |
90 ms |
9976 KB |
Output is correct |
27 |
Correct |
79 ms |
10460 KB |
Output is correct |
28 |
Correct |
86 ms |
10392 KB |
Output is correct |
29 |
Correct |
87 ms |
10104 KB |
Output is correct |
30 |
Correct |
78 ms |
10360 KB |
Output is correct |
31 |
Correct |
85 ms |
9848 KB |
Output is correct |
32 |
Correct |
80 ms |
9848 KB |
Output is correct |
33 |
Correct |
69 ms |
9308 KB |
Output is correct |
34 |
Correct |
72 ms |
9380 KB |
Output is correct |
35 |
Correct |
78 ms |
9336 KB |
Output is correct |
36 |
Correct |
97 ms |
9976 KB |
Output is correct |
37 |
Correct |
101 ms |
10076 KB |
Output is correct |
38 |
Correct |
73 ms |
10104 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5624 KB |
Output is correct |
2 |
Correct |
5 ms |
5496 KB |
Output is correct |
3 |
Correct |
5 ms |
5496 KB |
Output is correct |
4 |
Correct |
5 ms |
5496 KB |
Output is correct |
5 |
Correct |
7 ms |
5500 KB |
Output is correct |
6 |
Correct |
6 ms |
5624 KB |
Output is correct |
7 |
Correct |
6 ms |
5496 KB |
Output is correct |
8 |
Correct |
6 ms |
5496 KB |
Output is correct |
9 |
Correct |
6 ms |
5624 KB |
Output is correct |
10 |
Correct |
6 ms |
5496 KB |
Output is correct |
11 |
Correct |
6 ms |
5496 KB |
Output is correct |
12 |
Correct |
6 ms |
5496 KB |
Output is correct |
13 |
Correct |
6 ms |
5624 KB |
Output is correct |
14 |
Correct |
6 ms |
5628 KB |
Output is correct |
15 |
Correct |
6 ms |
5624 KB |
Output is correct |
16 |
Correct |
7 ms |
5496 KB |
Output is correct |
17 |
Correct |
6 ms |
5496 KB |
Output is correct |
18 |
Correct |
6 ms |
5624 KB |
Output is correct |
19 |
Correct |
6 ms |
5624 KB |
Output is correct |
20 |
Correct |
39 ms |
7672 KB |
Output is correct |
21 |
Correct |
39 ms |
7672 KB |
Output is correct |
22 |
Correct |
39 ms |
7672 KB |
Output is correct |
23 |
Correct |
39 ms |
7672 KB |
Output is correct |
24 |
Correct |
94 ms |
9564 KB |
Output is correct |
25 |
Correct |
98 ms |
9976 KB |
Output is correct |
26 |
Correct |
90 ms |
9976 KB |
Output is correct |
27 |
Correct |
79 ms |
10460 KB |
Output is correct |
28 |
Correct |
86 ms |
10392 KB |
Output is correct |
29 |
Correct |
87 ms |
10104 KB |
Output is correct |
30 |
Correct |
78 ms |
10360 KB |
Output is correct |
31 |
Correct |
85 ms |
9848 KB |
Output is correct |
32 |
Correct |
80 ms |
9848 KB |
Output is correct |
33 |
Correct |
69 ms |
9308 KB |
Output is correct |
34 |
Correct |
72 ms |
9380 KB |
Output is correct |
35 |
Correct |
78 ms |
9336 KB |
Output is correct |
36 |
Correct |
97 ms |
9976 KB |
Output is correct |
37 |
Correct |
101 ms |
10076 KB |
Output is correct |
38 |
Correct |
73 ms |
10104 KB |
Output is correct |
39 |
Execution timed out |
2041 ms |
10104 KB |
Time limit exceeded |
40 |
Halted |
0 ms |
0 KB |
- |