/**
* 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 = 320, 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++) {
^
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
263 ms |
254456 KB |
Output is correct |
2 |
Correct |
233 ms |
254500 KB |
Output is correct |
3 |
Correct |
219 ms |
254476 KB |
Output is correct |
4 |
Correct |
216 ms |
254556 KB |
Output is correct |
5 |
Correct |
251 ms |
254596 KB |
Output is correct |
6 |
Correct |
267 ms |
254504 KB |
Output is correct |
7 |
Correct |
267 ms |
254528 KB |
Output is correct |
8 |
Correct |
266 ms |
254456 KB |
Output is correct |
9 |
Correct |
272 ms |
254456 KB |
Output is correct |
10 |
Correct |
270 ms |
254456 KB |
Output is correct |
11 |
Correct |
273 ms |
254456 KB |
Output is correct |
12 |
Correct |
249 ms |
254584 KB |
Output is correct |
13 |
Correct |
223 ms |
254556 KB |
Output is correct |
14 |
Correct |
224 ms |
254456 KB |
Output is correct |
15 |
Correct |
219 ms |
254456 KB |
Output is correct |
16 |
Correct |
224 ms |
254456 KB |
Output is correct |
17 |
Correct |
223 ms |
254472 KB |
Output is correct |
18 |
Correct |
222 ms |
254584 KB |
Output is correct |
19 |
Correct |
220 ms |
254584 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
263 ms |
254456 KB |
Output is correct |
2 |
Correct |
233 ms |
254500 KB |
Output is correct |
3 |
Correct |
219 ms |
254476 KB |
Output is correct |
4 |
Correct |
216 ms |
254556 KB |
Output is correct |
5 |
Correct |
251 ms |
254596 KB |
Output is correct |
6 |
Correct |
267 ms |
254504 KB |
Output is correct |
7 |
Correct |
267 ms |
254528 KB |
Output is correct |
8 |
Correct |
266 ms |
254456 KB |
Output is correct |
9 |
Correct |
272 ms |
254456 KB |
Output is correct |
10 |
Correct |
270 ms |
254456 KB |
Output is correct |
11 |
Correct |
273 ms |
254456 KB |
Output is correct |
12 |
Correct |
249 ms |
254584 KB |
Output is correct |
13 |
Correct |
223 ms |
254556 KB |
Output is correct |
14 |
Correct |
224 ms |
254456 KB |
Output is correct |
15 |
Correct |
219 ms |
254456 KB |
Output is correct |
16 |
Correct |
224 ms |
254456 KB |
Output is correct |
17 |
Correct |
223 ms |
254472 KB |
Output is correct |
18 |
Correct |
222 ms |
254584 KB |
Output is correct |
19 |
Correct |
220 ms |
254584 KB |
Output is correct |
20 |
Correct |
615 ms |
256504 KB |
Output is correct |
21 |
Correct |
668 ms |
256632 KB |
Output is correct |
22 |
Correct |
625 ms |
256632 KB |
Output is correct |
23 |
Correct |
662 ms |
256604 KB |
Output is correct |
24 |
Correct |
784 ms |
258420 KB |
Output is correct |
25 |
Correct |
794 ms |
258684 KB |
Output is correct |
26 |
Correct |
782 ms |
258504 KB |
Output is correct |
27 |
Correct |
761 ms |
259064 KB |
Output is correct |
28 |
Correct |
747 ms |
258976 KB |
Output is correct |
29 |
Correct |
775 ms |
259036 KB |
Output is correct |
30 |
Correct |
880 ms |
259028 KB |
Output is correct |
31 |
Correct |
880 ms |
258808 KB |
Output is correct |
32 |
Correct |
795 ms |
258836 KB |
Output is correct |
33 |
Correct |
794 ms |
258272 KB |
Output is correct |
34 |
Correct |
825 ms |
258440 KB |
Output is correct |
35 |
Correct |
735 ms |
259076 KB |
Output is correct |
36 |
Correct |
779 ms |
259300 KB |
Output is correct |
37 |
Correct |
779 ms |
259284 KB |
Output is correct |
38 |
Correct |
750 ms |
259372 KB |
Output is correct |
# |
결과 |
실행 시간 |
메모리 |
Grader output |
1 |
Correct |
263 ms |
254456 KB |
Output is correct |
2 |
Correct |
233 ms |
254500 KB |
Output is correct |
3 |
Correct |
219 ms |
254476 KB |
Output is correct |
4 |
Correct |
216 ms |
254556 KB |
Output is correct |
5 |
Correct |
251 ms |
254596 KB |
Output is correct |
6 |
Correct |
267 ms |
254504 KB |
Output is correct |
7 |
Correct |
267 ms |
254528 KB |
Output is correct |
8 |
Correct |
266 ms |
254456 KB |
Output is correct |
9 |
Correct |
272 ms |
254456 KB |
Output is correct |
10 |
Correct |
270 ms |
254456 KB |
Output is correct |
11 |
Correct |
273 ms |
254456 KB |
Output is correct |
12 |
Correct |
249 ms |
254584 KB |
Output is correct |
13 |
Correct |
223 ms |
254556 KB |
Output is correct |
14 |
Correct |
224 ms |
254456 KB |
Output is correct |
15 |
Correct |
219 ms |
254456 KB |
Output is correct |
16 |
Correct |
224 ms |
254456 KB |
Output is correct |
17 |
Correct |
223 ms |
254472 KB |
Output is correct |
18 |
Correct |
222 ms |
254584 KB |
Output is correct |
19 |
Correct |
220 ms |
254584 KB |
Output is correct |
20 |
Correct |
615 ms |
256504 KB |
Output is correct |
21 |
Correct |
668 ms |
256632 KB |
Output is correct |
22 |
Correct |
625 ms |
256632 KB |
Output is correct |
23 |
Correct |
662 ms |
256604 KB |
Output is correct |
24 |
Correct |
784 ms |
258420 KB |
Output is correct |
25 |
Correct |
794 ms |
258684 KB |
Output is correct |
26 |
Correct |
782 ms |
258504 KB |
Output is correct |
27 |
Correct |
761 ms |
259064 KB |
Output is correct |
28 |
Correct |
747 ms |
258976 KB |
Output is correct |
29 |
Correct |
775 ms |
259036 KB |
Output is correct |
30 |
Correct |
880 ms |
259028 KB |
Output is correct |
31 |
Correct |
880 ms |
258808 KB |
Output is correct |
32 |
Correct |
795 ms |
258836 KB |
Output is correct |
33 |
Correct |
794 ms |
258272 KB |
Output is correct |
34 |
Correct |
825 ms |
258440 KB |
Output is correct |
35 |
Correct |
735 ms |
259076 KB |
Output is correct |
36 |
Correct |
779 ms |
259300 KB |
Output is correct |
37 |
Correct |
779 ms |
259284 KB |
Output is correct |
38 |
Correct |
750 ms |
259372 KB |
Output is correct |
39 |
Correct |
872 ms |
260168 KB |
Output is correct |
40 |
Correct |
898 ms |
260068 KB |
Output is correct |
41 |
Correct |
769 ms |
259832 KB |
Output is correct |
42 |
Correct |
1104 ms |
259064 KB |
Output is correct |
43 |
Correct |
955 ms |
259152 KB |
Output is correct |
44 |
Correct |
707 ms |
258052 KB |
Output is correct |
45 |
Incorrect |
631 ms |
257724 KB |
Output isn't correct |
46 |
Halted |
0 ms |
0 KB |
- |