# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
566768 | 2022-05-22T20:11:59 Z | milisav | Bitaro’s Party (JOI18_bitaro) | C++14 | 1872 ms | 277684 KB |
#include<bits/stdc++.h> #define maxn 300000 #define blk 320 using namespace std; int n,m,q; vector<int> a[maxn]; vector<int> b[maxn]; int city[maxn][blk]; int dist[maxn][blk]; int it[maxn]; int sz[maxn]; int c[maxn]; int ch[maxn]; bool fnd[maxn]; vector<int> topo; priority_queue<pair<int,int> > pq; bool ok[maxn]; void calc_small() { for(int iter=0;iter<n;iter++) { int u=topo[iter]; pq.push({0,u}); for(int i=0;i<b[u].size();i++) { it[b[u][i]]=0; pq.push({1+dist[b[u][i]][it[b[u][i]]],b[u][i]}); } while(sz[u]<blk && !pq.empty()) { int d=pq.top().first; int nd=pq.top().second; pq.pop(); int v=u; if(nd!=u) { v=city[nd][it[nd]]; it[nd]++; if(it[nd]<sz[nd]) pq.push({1+dist[nd][it[nd]],nd}); } if(!fnd[v]) { fnd[v]=true; dist[u][sz[u]]=d; city[u][sz[u]]=v; sz[u]++; } } while(!pq.empty()) pq.pop(); for(int i=0;i<sz[u];i++) fnd[city[u][i]]=false; } } int dst[maxn]; int calc_big(int t) { for(int i=1;i<=n;i++) dst[i]=-1; for(int iter=0;iter<n;iter++) { int u=topo[iter]; if(ok[u]) dst[u]=0; for(auto v:b[u]) { if(dst[v]!=-1) dst[u]=max(dst[u],dst[v]+1); } if(u==t) return dst[u]; } return -1; } int main() { scanf("%d %d %d",&n,&m,&q); for(int i=0;i<m;i++) { int s,e; scanf("%d %d",&s,&e); a[s].push_back(e); b[e].push_back(s); ch[e]++; } for(int i=1;i<=n;i++) { ok[i]=true; if(ch[i]==0) topo.push_back(i); } int iter=0; while(iter<topo.size()) { int u=topo[iter]; for(auto v:a[u]) { ch[v]--; if(ch[v]==0) topo.push_back(v); } iter++; } calc_small(); /*for(int i=1;i<=n;i++) { printf("%d %d\n",i,sz[i]); for(int j=0;j<sz[i];j++) { printf("\t%d %d\n",city[i][j],dist[i][j]); } }*/ for(int i=0;i<q;i++) { int t,y; scanf("%d %d",&t,&y); for(int j=0;j<y;j++) { scanf("%d",&c[j]); ok[c[j]]=false; } if(y<blk) { int ans=-1; for(int j=0;j<sz[t];j++) { if(ok[city[t][j]]) { ans=dist[t][j]; break; } } printf("%d\n",ans); } else { printf("%d\n",calc_big(t)); } for(int j=0;j<y;j++) { ok[c[j]]=true; } } return 0; }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 14420 KB | Output is correct |
2 | Correct | 9 ms | 14380 KB | Output is correct |
3 | Correct | 9 ms | 14356 KB | Output is correct |
4 | Correct | 7 ms | 14420 KB | Output is correct |
5 | Correct | 11 ms | 17008 KB | Output is correct |
6 | Correct | 11 ms | 17024 KB | Output is correct |
7 | Correct | 13 ms | 16912 KB | Output is correct |
8 | Correct | 19 ms | 17052 KB | Output is correct |
9 | Correct | 21 ms | 16964 KB | Output is correct |
10 | Correct | 18 ms | 16944 KB | Output is correct |
11 | Correct | 18 ms | 16980 KB | Output is correct |
12 | Correct | 15 ms | 16980 KB | Output is correct |
13 | Correct | 18 ms | 16984 KB | Output is correct |
14 | Correct | 15 ms | 16976 KB | Output is correct |
15 | Correct | 14 ms | 16980 KB | Output is correct |
16 | Correct | 16 ms | 17000 KB | Output is correct |
17 | Correct | 15 ms | 16980 KB | Output is correct |
18 | Correct | 15 ms | 16992 KB | Output is correct |
19 | Correct | 16 ms | 16980 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 14420 KB | Output is correct |
2 | Correct | 9 ms | 14380 KB | Output is correct |
3 | Correct | 9 ms | 14356 KB | Output is correct |
4 | Correct | 7 ms | 14420 KB | Output is correct |
5 | Correct | 11 ms | 17008 KB | Output is correct |
6 | Correct | 11 ms | 17024 KB | Output is correct |
7 | Correct | 13 ms | 16912 KB | Output is correct |
8 | Correct | 19 ms | 17052 KB | Output is correct |
9 | Correct | 21 ms | 16964 KB | Output is correct |
10 | Correct | 18 ms | 16944 KB | Output is correct |
11 | Correct | 18 ms | 16980 KB | Output is correct |
12 | Correct | 15 ms | 16980 KB | Output is correct |
13 | Correct | 18 ms | 16984 KB | Output is correct |
14 | Correct | 15 ms | 16976 KB | Output is correct |
15 | Correct | 14 ms | 16980 KB | Output is correct |
16 | Correct | 16 ms | 17000 KB | Output is correct |
17 | Correct | 15 ms | 16980 KB | Output is correct |
18 | Correct | 15 ms | 16992 KB | Output is correct |
19 | Correct | 16 ms | 16980 KB | Output is correct |
20 | Correct | 1630 ms | 19520 KB | Output is correct |
21 | Correct | 1269 ms | 19524 KB | Output is correct |
22 | Correct | 1612 ms | 19464 KB | Output is correct |
23 | Correct | 978 ms | 19416 KB | Output is correct |
24 | Correct | 1045 ms | 272492 KB | Output is correct |
25 | Correct | 1091 ms | 272452 KB | Output is correct |
26 | Correct | 1112 ms | 272512 KB | Output is correct |
27 | Correct | 1074 ms | 273832 KB | Output is correct |
28 | Correct | 1131 ms | 274064 KB | Output is correct |
29 | Correct | 1110 ms | 274096 KB | Output is correct |
30 | Correct | 1053 ms | 273148 KB | Output is correct |
31 | Correct | 1158 ms | 273180 KB | Output is correct |
32 | Correct | 1074 ms | 273276 KB | Output is correct |
33 | Correct | 774 ms | 273340 KB | Output is correct |
34 | Correct | 724 ms | 273280 KB | Output is correct |
35 | Correct | 783 ms | 273348 KB | Output is correct |
36 | Correct | 980 ms | 273372 KB | Output is correct |
37 | Correct | 936 ms | 273564 KB | Output is correct |
38 | Correct | 987 ms | 273408 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 14420 KB | Output is correct |
2 | Correct | 9 ms | 14380 KB | Output is correct |
3 | Correct | 9 ms | 14356 KB | Output is correct |
4 | Correct | 7 ms | 14420 KB | Output is correct |
5 | Correct | 11 ms | 17008 KB | Output is correct |
6 | Correct | 11 ms | 17024 KB | Output is correct |
7 | Correct | 13 ms | 16912 KB | Output is correct |
8 | Correct | 19 ms | 17052 KB | Output is correct |
9 | Correct | 21 ms | 16964 KB | Output is correct |
10 | Correct | 18 ms | 16944 KB | Output is correct |
11 | Correct | 18 ms | 16980 KB | Output is correct |
12 | Correct | 15 ms | 16980 KB | Output is correct |
13 | Correct | 18 ms | 16984 KB | Output is correct |
14 | Correct | 15 ms | 16976 KB | Output is correct |
15 | Correct | 14 ms | 16980 KB | Output is correct |
16 | Correct | 16 ms | 17000 KB | Output is correct |
17 | Correct | 15 ms | 16980 KB | Output is correct |
18 | Correct | 15 ms | 16992 KB | Output is correct |
19 | Correct | 16 ms | 16980 KB | Output is correct |
20 | Correct | 1630 ms | 19520 KB | Output is correct |
21 | Correct | 1269 ms | 19524 KB | Output is correct |
22 | Correct | 1612 ms | 19464 KB | Output is correct |
23 | Correct | 978 ms | 19416 KB | Output is correct |
24 | Correct | 1045 ms | 272492 KB | Output is correct |
25 | Correct | 1091 ms | 272452 KB | Output is correct |
26 | Correct | 1112 ms | 272512 KB | Output is correct |
27 | Correct | 1074 ms | 273832 KB | Output is correct |
28 | Correct | 1131 ms | 274064 KB | Output is correct |
29 | Correct | 1110 ms | 274096 KB | Output is correct |
30 | Correct | 1053 ms | 273148 KB | Output is correct |
31 | Correct | 1158 ms | 273180 KB | Output is correct |
32 | Correct | 1074 ms | 273276 KB | Output is correct |
33 | Correct | 774 ms | 273340 KB | Output is correct |
34 | Correct | 724 ms | 273280 KB | Output is correct |
35 | Correct | 783 ms | 273348 KB | Output is correct |
36 | Correct | 980 ms | 273372 KB | Output is correct |
37 | Correct | 936 ms | 273564 KB | Output is correct |
38 | Correct | 987 ms | 273408 KB | Output is correct |
39 | Correct | 1109 ms | 272160 KB | Output is correct |
40 | Correct | 1042 ms | 271988 KB | Output is correct |
41 | Correct | 1111 ms | 271992 KB | Output is correct |
42 | Correct | 1218 ms | 272344 KB | Output is correct |
43 | Correct | 1087 ms | 272472 KB | Output is correct |
44 | Correct | 1712 ms | 19948 KB | Output is correct |
45 | Correct | 1714 ms | 21424 KB | Output is correct |
46 | Correct | 1646 ms | 21292 KB | Output is correct |
47 | Correct | 1630 ms | 21112 KB | Output is correct |
48 | Correct | 1643 ms | 21136 KB | Output is correct |
49 | Correct | 1126 ms | 277148 KB | Output is correct |
50 | Correct | 1111 ms | 276008 KB | Output is correct |
51 | Correct | 1256 ms | 22212 KB | Output is correct |
52 | Correct | 1384 ms | 21364 KB | Output is correct |
53 | Correct | 1132 ms | 276464 KB | Output is correct |
54 | Correct | 1086 ms | 276444 KB | Output is correct |
55 | Correct | 1028 ms | 275580 KB | Output is correct |
56 | Correct | 1050 ms | 275388 KB | Output is correct |
57 | Correct | 1776 ms | 22160 KB | Output is correct |
58 | Correct | 1872 ms | 22076 KB | Output is correct |
59 | Correct | 1720 ms | 21288 KB | Output is correct |
60 | Correct | 1595 ms | 21276 KB | Output is correct |
61 | Correct | 1219 ms | 276508 KB | Output is correct |
62 | Correct | 1076 ms | 275980 KB | Output is correct |
63 | Correct | 1063 ms | 275972 KB | Output is correct |
64 | Correct | 1272 ms | 276404 KB | Output is correct |
65 | Correct | 1253 ms | 275988 KB | Output is correct |
66 | Correct | 1189 ms | 275924 KB | Output is correct |
67 | Correct | 1080 ms | 275964 KB | Output is correct |
68 | Correct | 958 ms | 275448 KB | Output is correct |
69 | Correct | 920 ms | 275512 KB | Output is correct |
70 | Correct | 1095 ms | 276548 KB | Output is correct |
71 | Correct | 967 ms | 276056 KB | Output is correct |
72 | Correct | 955 ms | 276044 KB | Output is correct |
73 | Correct | 1172 ms | 276424 KB | Output is correct |
74 | Correct | 995 ms | 275992 KB | Output is correct |
75 | Correct | 993 ms | 275916 KB | Output is correct |
76 | Correct | 1149 ms | 277684 KB | Output is correct |
77 | Correct | 1086 ms | 276252 KB | Output is correct |
78 | Correct | 1088 ms | 276644 KB | Output is correct |
79 | Correct | 1253 ms | 22300 KB | Output is correct |
80 | Correct | 1224 ms | 21360 KB | Output is correct |
81 | Correct | 1222 ms | 20900 KB | Output is correct |
82 | Correct | 1138 ms | 276800 KB | Output is correct |
83 | Correct | 1151 ms | 276616 KB | Output is correct |
84 | Correct | 1088 ms | 275536 KB | Output is correct |
85 | Correct | 1096 ms | 275536 KB | Output is correct |
86 | Correct | 1071 ms | 276116 KB | Output is correct |
87 | Correct | 1182 ms | 276088 KB | Output is correct |
88 | Correct | 1574 ms | 22320 KB | Output is correct |
89 | Correct | 1666 ms | 22252 KB | Output is correct |
90 | Correct | 1601 ms | 21504 KB | Output is correct |
91 | Correct | 1575 ms | 21436 KB | Output is correct |
92 | Correct | 1543 ms | 21208 KB | Output is correct |
93 | Correct | 1651 ms | 21096 KB | Output is correct |
94 | Correct | 850 ms | 276792 KB | Output is correct |
95 | Correct | 738 ms | 276580 KB | Output is correct |
96 | Correct | 782 ms | 275644 KB | Output is correct |
97 | Correct | 739 ms | 275540 KB | Output is correct |
98 | Correct | 791 ms | 276040 KB | Output is correct |
99 | Correct | 736 ms | 276140 KB | Output is correct |
100 | Correct | 1142 ms | 22348 KB | Output is correct |
101 | Correct | 872 ms | 22368 KB | Output is correct |
102 | Correct | 973 ms | 21296 KB | Output is correct |
103 | Correct | 921 ms | 21352 KB | Output is correct |
104 | Correct | 1010 ms | 20928 KB | Output is correct |
105 | Correct | 933 ms | 21100 KB | Output is correct |
106 | Correct | 1020 ms | 276936 KB | Output is correct |
107 | Correct | 976 ms | 276816 KB | Output is correct |
108 | Correct | 926 ms | 275848 KB | Output is correct |
109 | Correct | 898 ms | 275696 KB | Output is correct |
110 | Correct | 946 ms | 276232 KB | Output is correct |
111 | Correct | 936 ms | 276172 KB | Output is correct |
112 | Correct | 1526 ms | 22392 KB | Output is correct |
113 | Correct | 1547 ms | 22292 KB | Output is correct |
114 | Correct | 1541 ms | 21540 KB | Output is correct |
115 | Correct | 1560 ms | 21392 KB | Output is correct |
116 | Correct | 1431 ms | 21084 KB | Output is correct |
117 | Correct | 1614 ms | 20976 KB | Output is correct |
118 | Correct | 1034 ms | 276000 KB | Output is correct |
119 | Correct | 913 ms | 275508 KB | Output is correct |
120 | Correct | 900 ms | 275568 KB | Output is correct |
121 | Correct | 1042 ms | 275984 KB | Output is correct |
122 | Correct | 931 ms | 275416 KB | Output is correct |
123 | Correct | 891 ms | 275408 KB | Output is correct |
124 | Correct | 1031 ms | 276004 KB | Output is correct |
125 | Correct | 920 ms | 275608 KB | Output is correct |
126 | Correct | 977 ms | 275364 KB | Output is correct |