#include <bits/stdc++.h>
#define ll long long
#define ull unsigned ll
#define pb push_back
#define pa pair<int, int>
#define pall pair<ll, int>
#define fi first
#define se second
#define TASK "test"
#define all(x) x.begin(), x.end()
using namespace std;
template<typename T1, typename T2> bool mini (T1 &a, T2 b) {if(a > b) a = b; else return 0; return 1;}
template<typename T1, typename T2> bool maxi (T1 &a, T2 b) {if(a < b) a = b; else return 0; return 1;}
const int MOD = 1e9 + 7;
const int LOG = 20;
const int maxn = 1e5 + 7;
const ll oo = 1e15 + 69;
const int sz = 320;
int n, m, q, u, v, t, y, c, id[maxn], d[maxn];
bool vis[maxn];
pa f[sz][maxn], check[sz];
vector<int> g[maxn], topo, arc[maxn];
void dfs(int u) {
vis[u] = 1;
for(auto v:g[u])
if(!vis[v]) dfs(v);
topo.pb(u);
}
int main() {
ios_base::sync_with_stdio(false);
cin.tie(NULL);
//freopen(TASK".inp", "r", stdin);
//freopen(TASK".out", "w", stdout);
cin>>n>>m>>q;
while(m--) {
cin>>u>>v;
g[u].pb(v);
arc[v].pb(u);
}
for(int i = 1; i <= n; i++)
if(!vis[i]) dfs(i);
reverse(all(topo));
for(int i = 1; i <= n; i++)
for(int j = 0; j < sz; j++) f[j][i] = {0, (j == 0 ? i:-1)};
for(auto u:topo) {
for(auto v:g[u]) {
int j = 0;
fill_n(check, sz, make_pair(-1, -1));
for(int i = 0; i < sz; i++) {
if(i && check[i - 1].fi != -1) {
check[i] = f[i][v];
f[i][v] = check[i - 1];
}
while(j < sz && f[j][u].se != -1 && f[j][u].fi + 1 <= f[i][v].fi) j++;
if(j < sz && f[j][u].se != -1 && f[j][u].fi + 1 > f[i][v].fi) {
check[i] = f[i][v];
f[i][v] = {f[j][u].fi + 1, f[j][u].se};
j++;
}
}
}
}
for(int k = 1; k <= q; k++) {
cin>>t>>y;
for(int i = 0; i < y; i++) {
cin>>c;
id[c] = k;
}
if(y >= sz) {
fill_n(d, n + 1, -1);
d[t] = 0;
int ans = -1;
if(id[t] != k) ans = 0;
bool ok = 0;
for(int i = topo.size() - 1; i >= 0; i--) {
int u = topo[i];
if(d[u] == -1 || (u != t && !ok)) continue;
if(u > t) continue;
if(u == t) ok = 1;
for(auto v:arc[u]) {
maxi(d[v], d[u] + 1);
if(v <= t && id[v] != k) maxi(ans, d[v]);
}
}
cout<<ans<<"\n";
} else {
int ans = -1;
for(int i = 0; i < sz; i++) {
int u = f[i][t].se;
if(u == -1 || id[u] == k || u > t) continue;
maxi(ans, f[i][t].fi);
}
cout<<ans<<"\n";
}
}
return 0;
}
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6740 KB |
Output is correct |
2 |
Correct |
4 ms |
6688 KB |
Output is correct |
3 |
Correct |
3 ms |
6740 KB |
Output is correct |
4 |
Correct |
3 ms |
6692 KB |
Output is correct |
5 |
Correct |
7 ms |
9300 KB |
Output is correct |
6 |
Correct |
8 ms |
9300 KB |
Output is correct |
7 |
Correct |
9 ms |
9260 KB |
Output is correct |
8 |
Correct |
8 ms |
9428 KB |
Output is correct |
9 |
Correct |
7 ms |
9428 KB |
Output is correct |
10 |
Correct |
7 ms |
9428 KB |
Output is correct |
11 |
Correct |
8 ms |
9300 KB |
Output is correct |
12 |
Correct |
8 ms |
9388 KB |
Output is correct |
13 |
Correct |
7 ms |
9268 KB |
Output is correct |
14 |
Correct |
8 ms |
9300 KB |
Output is correct |
15 |
Correct |
7 ms |
9300 KB |
Output is correct |
16 |
Correct |
8 ms |
9300 KB |
Output is correct |
17 |
Correct |
7 ms |
9392 KB |
Output is correct |
18 |
Correct |
9 ms |
9300 KB |
Output is correct |
19 |
Correct |
9 ms |
9384 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6740 KB |
Output is correct |
2 |
Correct |
4 ms |
6688 KB |
Output is correct |
3 |
Correct |
3 ms |
6740 KB |
Output is correct |
4 |
Correct |
3 ms |
6692 KB |
Output is correct |
5 |
Correct |
7 ms |
9300 KB |
Output is correct |
6 |
Correct |
8 ms |
9300 KB |
Output is correct |
7 |
Correct |
9 ms |
9260 KB |
Output is correct |
8 |
Correct |
8 ms |
9428 KB |
Output is correct |
9 |
Correct |
7 ms |
9428 KB |
Output is correct |
10 |
Correct |
7 ms |
9428 KB |
Output is correct |
11 |
Correct |
8 ms |
9300 KB |
Output is correct |
12 |
Correct |
8 ms |
9388 KB |
Output is correct |
13 |
Correct |
7 ms |
9268 KB |
Output is correct |
14 |
Correct |
8 ms |
9300 KB |
Output is correct |
15 |
Correct |
7 ms |
9300 KB |
Output is correct |
16 |
Correct |
8 ms |
9300 KB |
Output is correct |
17 |
Correct |
7 ms |
9392 KB |
Output is correct |
18 |
Correct |
9 ms |
9300 KB |
Output is correct |
19 |
Correct |
9 ms |
9384 KB |
Output is correct |
20 |
Correct |
334 ms |
12200 KB |
Output is correct |
21 |
Correct |
282 ms |
12252 KB |
Output is correct |
22 |
Correct |
273 ms |
12108 KB |
Output is correct |
23 |
Correct |
274 ms |
12260 KB |
Output is correct |
24 |
Correct |
1371 ms |
264648 KB |
Output is correct |
25 |
Correct |
1365 ms |
264752 KB |
Output is correct |
26 |
Correct |
1331 ms |
264392 KB |
Output is correct |
27 |
Correct |
1082 ms |
270900 KB |
Output is correct |
28 |
Correct |
1104 ms |
270876 KB |
Output is correct |
29 |
Correct |
1092 ms |
270532 KB |
Output is correct |
30 |
Correct |
1131 ms |
265544 KB |
Output is correct |
31 |
Correct |
1377 ms |
265412 KB |
Output is correct |
32 |
Correct |
1081 ms |
265248 KB |
Output is correct |
33 |
Correct |
1196 ms |
266312 KB |
Output is correct |
34 |
Correct |
1285 ms |
265412 KB |
Output is correct |
35 |
Correct |
1184 ms |
266136 KB |
Output is correct |
36 |
Correct |
1272 ms |
266376 KB |
Output is correct |
37 |
Correct |
1359 ms |
265524 KB |
Output is correct |
38 |
Correct |
1272 ms |
266128 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
5 ms |
6740 KB |
Output is correct |
2 |
Correct |
4 ms |
6688 KB |
Output is correct |
3 |
Correct |
3 ms |
6740 KB |
Output is correct |
4 |
Correct |
3 ms |
6692 KB |
Output is correct |
5 |
Correct |
7 ms |
9300 KB |
Output is correct |
6 |
Correct |
8 ms |
9300 KB |
Output is correct |
7 |
Correct |
9 ms |
9260 KB |
Output is correct |
8 |
Correct |
8 ms |
9428 KB |
Output is correct |
9 |
Correct |
7 ms |
9428 KB |
Output is correct |
10 |
Correct |
7 ms |
9428 KB |
Output is correct |
11 |
Correct |
8 ms |
9300 KB |
Output is correct |
12 |
Correct |
8 ms |
9388 KB |
Output is correct |
13 |
Correct |
7 ms |
9268 KB |
Output is correct |
14 |
Correct |
8 ms |
9300 KB |
Output is correct |
15 |
Correct |
7 ms |
9300 KB |
Output is correct |
16 |
Correct |
8 ms |
9300 KB |
Output is correct |
17 |
Correct |
7 ms |
9392 KB |
Output is correct |
18 |
Correct |
9 ms |
9300 KB |
Output is correct |
19 |
Correct |
9 ms |
9384 KB |
Output is correct |
20 |
Correct |
334 ms |
12200 KB |
Output is correct |
21 |
Correct |
282 ms |
12252 KB |
Output is correct |
22 |
Correct |
273 ms |
12108 KB |
Output is correct |
23 |
Correct |
274 ms |
12260 KB |
Output is correct |
24 |
Correct |
1371 ms |
264648 KB |
Output is correct |
25 |
Correct |
1365 ms |
264752 KB |
Output is correct |
26 |
Correct |
1331 ms |
264392 KB |
Output is correct |
27 |
Correct |
1082 ms |
270900 KB |
Output is correct |
28 |
Correct |
1104 ms |
270876 KB |
Output is correct |
29 |
Correct |
1092 ms |
270532 KB |
Output is correct |
30 |
Correct |
1131 ms |
265544 KB |
Output is correct |
31 |
Correct |
1377 ms |
265412 KB |
Output is correct |
32 |
Correct |
1081 ms |
265248 KB |
Output is correct |
33 |
Correct |
1196 ms |
266312 KB |
Output is correct |
34 |
Correct |
1285 ms |
265412 KB |
Output is correct |
35 |
Correct |
1184 ms |
266136 KB |
Output is correct |
36 |
Correct |
1272 ms |
266376 KB |
Output is correct |
37 |
Correct |
1359 ms |
265524 KB |
Output is correct |
38 |
Correct |
1272 ms |
266128 KB |
Output is correct |
39 |
Correct |
1780 ms |
265076 KB |
Output is correct |
40 |
Incorrect |
1387 ms |
264652 KB |
Output isn't correct |
41 |
Halted |
0 ms |
0 KB |
- |