#include <bits/stdc++.h>
using namespace std;
#define fo(i,s,t) for(int i = s; i <= t; ++ i)
#define fd(i,s,t) for(int i = s; i >= t; -- i)
#define bf(i,s) for(int i = head[s]; i; i = e[i].next)
#define mp make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define VI vector<int>
#define sf scanf
#define pf printf
#define fp freopen
#define SZ(x) ((int)(x).size())
#ifdef MPS
#define D(x...) printf(x)
#else
#define D(x...)
#endif
typedef long long ll;
typedef double db;
typedef unsigned long long ull;
const int inf = 1<<30;
const ll INF = 1ll<<60;
const db Inf = 1e20;
const db eps = 1e-9;
void gmax(int &a,int b){a = (a > b ? a : b);}
void gmin(int &a,int b){a = (a < b ? a : b);}
const int maxn = 100050;
int n, m, q, cnt[maxn], in[maxn], gg[maxn];
VI adj[maxn], adj2[maxn];
pii dp[maxn][321], tmpa[321], tmpb[321];
bool g[maxn], banned[maxn];
int dist[maxn], vis[maxn], T;
queue<int> Q;
int dfs(int u)
{
if(vis[u] == T) return dist[u];
vis[u] = T; dist[u] = (banned[u] == true?-inf:0);
for(auto p : adj2[u]) dist[u] = max(dist[u], dfs(p) + 1);
return dist[u];
}
void bfs(int u)
{
++ T;
pf("%d\n", max(-1,dfs(u)));
}
int main()
{
#ifdef MPS
freopen("03-140.txt","r",stdin);
freopen("1.out","w",stdout);
#endif
sf("%d%d%d",&n,&m,&q);
fo(i,1,m)
{
int u, v;
sf("%d%d",&u,&v);
adj[u].pb(v); in[v] ++;
adj2[v].pb(u);
}
fo(i,1,n) if(!in[i]) Q.push(i);
while(!Q.empty())
{
int h = Q.front(); Q.pop();
dp[h][++cnt[h]] = mp(h, 0);
for(auto p : adj[h])
{
fo(j,1,cnt[h]) {tmpa[j] = dp[h][j]; tmpa[j].se ++;}
fo(j,1,cnt[p]) tmpb[j] = dp[p][j];
int p1 = 1, p2 = 1, num = 0;
while(p1 <= cnt[h] && p2 <= cnt[p] && num < 320)
{
if(g[tmpa[p1].fi]) {++p1; continue;}
if(g[tmpb[p2].fi]) {++p2; continue;}
if(tmpa[p1].se > tmpb[p2].se) {g[tmpa[p1].fi] = true; dp[p][++num] = tmpa[p1++];}
else {g[tmpb[p2].fi] = true; dp[p][++num] = tmpb[p2++];}
}
while(p1 <= cnt[h] && num < 320) {if(g[tmpa[p1].fi]) {++p1; continue;} g[tmpa[p1].fi] = true; dp[p][++num] = tmpa[p1++];}
while(p2 <= cnt[p] && num < 320) {if(g[tmpb[p2].fi]) {++p2; continue;} g[tmpb[p2].fi] = true; dp[p][++num] = tmpb[p2++];}
cnt[p] = num;
fo(i,1,num) g[dp[p][i].fi] = false;
if(!(--in[p])) Q.push(p);
}
}
while(q-- )
{
int x, y;
sf("%d%d",&x,&y);
fo(i,1,y) {sf("%d",&gg[i]); banned[gg[i]] = true;}
if(y > 320) bfs(x);
else {fo(i,1,cnt[x]) if(!banned[dp[x][i].fi]) {pf("%d\n",dp[x][i].se); goto loop;} puts("-1"); loop:;}
fo(i,1,y) banned[gg[i]] = false;
}
return 0;
}
Compilation message
bitaro.cpp: In function 'int main()':
bitaro.cpp:60:4: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
sf("%d%d%d",&n,&m,&q);
^
bitaro.cpp:64:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
sf("%d%d",&u,&v);
^
bitaro.cpp:95:5: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
sf("%d%d",&x,&y);
^
bitaro.cpp:96:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
fo(i,1,y) {sf("%d",&gg[i]); banned[gg[i]] = true;}
^
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
6 ms |
5392 KB |
Output is correct |
4 |
Correct |
7 ms |
5392 KB |
Output is correct |
5 |
Correct |
12 ms |
7864 KB |
Output is correct |
6 |
Correct |
12 ms |
7864 KB |
Output is correct |
7 |
Correct |
13 ms |
7864 KB |
Output is correct |
8 |
Correct |
13 ms |
7864 KB |
Output is correct |
9 |
Correct |
14 ms |
7896 KB |
Output is correct |
10 |
Correct |
13 ms |
7900 KB |
Output is correct |
11 |
Correct |
12 ms |
7900 KB |
Output is correct |
12 |
Correct |
10 ms |
8028 KB |
Output is correct |
13 |
Correct |
11 ms |
8028 KB |
Output is correct |
14 |
Correct |
11 ms |
8028 KB |
Output is correct |
15 |
Correct |
11 ms |
8028 KB |
Output is correct |
16 |
Correct |
11 ms |
8028 KB |
Output is correct |
17 |
Correct |
13 ms |
8028 KB |
Output is correct |
18 |
Correct |
12 ms |
8028 KB |
Output is correct |
19 |
Correct |
13 ms |
8028 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
6 ms |
5392 KB |
Output is correct |
4 |
Correct |
7 ms |
5392 KB |
Output is correct |
5 |
Correct |
12 ms |
7864 KB |
Output is correct |
6 |
Correct |
12 ms |
7864 KB |
Output is correct |
7 |
Correct |
13 ms |
7864 KB |
Output is correct |
8 |
Correct |
13 ms |
7864 KB |
Output is correct |
9 |
Correct |
14 ms |
7896 KB |
Output is correct |
10 |
Correct |
13 ms |
7900 KB |
Output is correct |
11 |
Correct |
12 ms |
7900 KB |
Output is correct |
12 |
Correct |
10 ms |
8028 KB |
Output is correct |
13 |
Correct |
11 ms |
8028 KB |
Output is correct |
14 |
Correct |
11 ms |
8028 KB |
Output is correct |
15 |
Correct |
11 ms |
8028 KB |
Output is correct |
16 |
Correct |
11 ms |
8028 KB |
Output is correct |
17 |
Correct |
13 ms |
8028 KB |
Output is correct |
18 |
Correct |
12 ms |
8028 KB |
Output is correct |
19 |
Correct |
13 ms |
8028 KB |
Output is correct |
20 |
Correct |
423 ms |
10364 KB |
Output is correct |
21 |
Correct |
407 ms |
10460 KB |
Output is correct |
22 |
Correct |
396 ms |
10460 KB |
Output is correct |
23 |
Correct |
493 ms |
10460 KB |
Output is correct |
24 |
Correct |
984 ms |
263136 KB |
Output is correct |
25 |
Correct |
955 ms |
263424 KB |
Output is correct |
26 |
Correct |
1075 ms |
263424 KB |
Output is correct |
27 |
Correct |
1018 ms |
266552 KB |
Output is correct |
28 |
Correct |
1041 ms |
266744 KB |
Output is correct |
29 |
Correct |
1049 ms |
267736 KB |
Output is correct |
30 |
Correct |
1016 ms |
267736 KB |
Output is correct |
31 |
Correct |
1141 ms |
267736 KB |
Output is correct |
32 |
Correct |
1008 ms |
267736 KB |
Output is correct |
33 |
Correct |
890 ms |
267736 KB |
Output is correct |
34 |
Correct |
888 ms |
267736 KB |
Output is correct |
35 |
Correct |
812 ms |
267736 KB |
Output is correct |
36 |
Correct |
941 ms |
267736 KB |
Output is correct |
37 |
Correct |
910 ms |
267736 KB |
Output is correct |
38 |
Correct |
933 ms |
267736 KB |
Output is correct |
# |
Verdict |
Execution time |
Memory |
Grader output |
1 |
Correct |
6 ms |
5112 KB |
Output is correct |
2 |
Correct |
6 ms |
5244 KB |
Output is correct |
3 |
Correct |
6 ms |
5392 KB |
Output is correct |
4 |
Correct |
7 ms |
5392 KB |
Output is correct |
5 |
Correct |
12 ms |
7864 KB |
Output is correct |
6 |
Correct |
12 ms |
7864 KB |
Output is correct |
7 |
Correct |
13 ms |
7864 KB |
Output is correct |
8 |
Correct |
13 ms |
7864 KB |
Output is correct |
9 |
Correct |
14 ms |
7896 KB |
Output is correct |
10 |
Correct |
13 ms |
7900 KB |
Output is correct |
11 |
Correct |
12 ms |
7900 KB |
Output is correct |
12 |
Correct |
10 ms |
8028 KB |
Output is correct |
13 |
Correct |
11 ms |
8028 KB |
Output is correct |
14 |
Correct |
11 ms |
8028 KB |
Output is correct |
15 |
Correct |
11 ms |
8028 KB |
Output is correct |
16 |
Correct |
11 ms |
8028 KB |
Output is correct |
17 |
Correct |
13 ms |
8028 KB |
Output is correct |
18 |
Correct |
12 ms |
8028 KB |
Output is correct |
19 |
Correct |
13 ms |
8028 KB |
Output is correct |
20 |
Correct |
423 ms |
10364 KB |
Output is correct |
21 |
Correct |
407 ms |
10460 KB |
Output is correct |
22 |
Correct |
396 ms |
10460 KB |
Output is correct |
23 |
Correct |
493 ms |
10460 KB |
Output is correct |
24 |
Correct |
984 ms |
263136 KB |
Output is correct |
25 |
Correct |
955 ms |
263424 KB |
Output is correct |
26 |
Correct |
1075 ms |
263424 KB |
Output is correct |
27 |
Correct |
1018 ms |
266552 KB |
Output is correct |
28 |
Correct |
1041 ms |
266744 KB |
Output is correct |
29 |
Correct |
1049 ms |
267736 KB |
Output is correct |
30 |
Correct |
1016 ms |
267736 KB |
Output is correct |
31 |
Correct |
1141 ms |
267736 KB |
Output is correct |
32 |
Correct |
1008 ms |
267736 KB |
Output is correct |
33 |
Correct |
890 ms |
267736 KB |
Output is correct |
34 |
Correct |
888 ms |
267736 KB |
Output is correct |
35 |
Correct |
812 ms |
267736 KB |
Output is correct |
36 |
Correct |
941 ms |
267736 KB |
Output is correct |
37 |
Correct |
910 ms |
267736 KB |
Output is correct |
38 |
Correct |
933 ms |
267736 KB |
Output is correct |
39 |
Correct |
1020 ms |
267736 KB |
Output is correct |
40 |
Correct |
1000 ms |
267736 KB |
Output is correct |
41 |
Correct |
1045 ms |
267736 KB |
Output is correct |
42 |
Correct |
1121 ms |
267736 KB |
Output is correct |
43 |
Correct |
1107 ms |
267736 KB |
Output is correct |
44 |
Correct |
461 ms |
267736 KB |
Output is correct |
45 |
Correct |
435 ms |
267736 KB |
Output is correct |
46 |
Correct |
440 ms |
267736 KB |
Output is correct |
47 |
Correct |
451 ms |
267736 KB |
Output is correct |
48 |
Correct |
431 ms |
267736 KB |
Output is correct |
49 |
Correct |
1073 ms |
267736 KB |
Output is correct |
50 |
Correct |
914 ms |
267736 KB |
Output is correct |
51 |
Correct |
444 ms |
267736 KB |
Output is correct |
52 |
Correct |
414 ms |
267736 KB |
Output is correct |
53 |
Correct |
952 ms |
267736 KB |
Output is correct |
54 |
Correct |
962 ms |
267736 KB |
Output is correct |
55 |
Correct |
1097 ms |
267736 KB |
Output is correct |
56 |
Correct |
952 ms |
267736 KB |
Output is correct |
57 |
Correct |
480 ms |
267736 KB |
Output is correct |
58 |
Correct |
469 ms |
267736 KB |
Output is correct |
59 |
Correct |
439 ms |
267736 KB |
Output is correct |
60 |
Correct |
436 ms |
267736 KB |
Output is correct |
61 |
Correct |
1697 ms |
268108 KB |
Output is correct |
62 |
Correct |
1623 ms |
268108 KB |
Output is correct |
63 |
Correct |
1203 ms |
268108 KB |
Output is correct |
64 |
Execution timed out |
2095 ms |
268108 KB |
Time limit exceeded |
65 |
Halted |
0 ms |
0 KB |
- |