# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
888056 | 2023-12-15T20:58:15 Z | PM1 | Bitaro’s Party (JOI18_bitaro) | C++17 | 657 ms | 214608 KB |
#include <bits/stdc++.h> using namespace std; #define fr first #define sc second const int mxn=1e5+5,sq=130; int n,m,q,mark[mxn]; vector<int>v[mxn]; vector<pair<int,int> >pre[mxn]; int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); cin>>n>>m>>q; for(int i=1;i<=m;i++){ int x,y; cin>>x>>y; v[y].push_back(x); } for(int i=1;i<=n;i++){ int p[v[i].size()]; memset(p,0,sizeof p); pair<int,int>num; while(pre[i].size()<sq){ for(int j=0;j<v[i].size();j++){ int x=v[i][j]; if(p[j]>=pre[x].size() )continue; while( p[j]<pre[x].size()&&mark[pre[x][p[j]].fr] )p[j]++;//cout<<j<<" "<<p[j]<<endl; if(p[j]>=pre[x].size())continue; if(pre[x][p[j]].sc+1>=num.sc){ num.sc=pre[x][p[j]].sc+1; num.fr=pre[x][p[j]].fr; } } if(num.fr==0)break; mark[num.fr]=1; pre[i].push_back(num); num={0,0}; } if(pre[i].size()<sq){ pre[i].push_back({i,0}); mark[i]=1; } for(auto j:pre[i]){ mark[j.fr]=0; } for(int j=2;j<pre[i].size();j++){ assert(pre[i][j].sc<=pre[i][j-1].sc); } } while(q--){ int t,y; cin>>t>>y; int a[y]; for(int i=0;i<y;i++){ cin>>a[i]; mark[a[i]]=1; } if(y>=sq){ int dp[t+1]; for(int i=1;i<=t;i++){ dp[i]=(mark[i])?-1e6:0; for(auto j:v[i]){ dp[i]=max(dp[i],dp[j]+1); } } if(dp[t]<0)dp[t]=-1; cout<<dp[t]<<'\n'; } else{ int d=0; for(auto i:pre[t]){ if(!mark[i.fr]){ d=1; cout<<i.sc<<'\n'; break; } } if(!d) cout<<-1<<'\n'; } for(int i=0;i<y;i++) mark[a[i]]=0; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4952 KB | Output is correct |
2 | Correct | 1 ms | 5036 KB | Output is correct |
3 | Correct | 1 ms | 4956 KB | Output is correct |
4 | Correct | 2 ms | 4956 KB | Output is correct |
5 | Correct | 4 ms | 5468 KB | Output is correct |
6 | Correct | 3 ms | 5532 KB | Output is correct |
7 | Correct | 3 ms | 5468 KB | Output is correct |
8 | Correct | 5 ms | 7032 KB | Output is correct |
9 | Correct | 5 ms | 7000 KB | Output is correct |
10 | Correct | 6 ms | 7256 KB | Output is correct |
11 | Correct | 5 ms | 6844 KB | Output is correct |
12 | Correct | 3 ms | 6236 KB | Output is correct |
13 | Correct | 7 ms | 6748 KB | Output is correct |
14 | Correct | 4 ms | 6236 KB | Output is correct |
15 | Correct | 3 ms | 5724 KB | Output is correct |
16 | Correct | 3 ms | 6236 KB | Output is correct |
17 | Correct | 4 ms | 6232 KB | Output is correct |
18 | Correct | 3 ms | 5980 KB | Output is correct |
19 | Correct | 4 ms | 6492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4952 KB | Output is correct |
2 | Correct | 1 ms | 5036 KB | Output is correct |
3 | Correct | 1 ms | 4956 KB | Output is correct |
4 | Correct | 2 ms | 4956 KB | Output is correct |
5 | Correct | 4 ms | 5468 KB | Output is correct |
6 | Correct | 3 ms | 5532 KB | Output is correct |
7 | Correct | 3 ms | 5468 KB | Output is correct |
8 | Correct | 5 ms | 7032 KB | Output is correct |
9 | Correct | 5 ms | 7000 KB | Output is correct |
10 | Correct | 6 ms | 7256 KB | Output is correct |
11 | Correct | 5 ms | 6844 KB | Output is correct |
12 | Correct | 3 ms | 6236 KB | Output is correct |
13 | Correct | 7 ms | 6748 KB | Output is correct |
14 | Correct | 4 ms | 6236 KB | Output is correct |
15 | Correct | 3 ms | 5724 KB | Output is correct |
16 | Correct | 3 ms | 6236 KB | Output is correct |
17 | Correct | 4 ms | 6232 KB | Output is correct |
18 | Correct | 3 ms | 5980 KB | Output is correct |
19 | Correct | 4 ms | 6492 KB | Output is correct |
20 | Correct | 135 ms | 7940 KB | Output is correct |
21 | Correct | 134 ms | 8016 KB | Output is correct |
22 | Correct | 130 ms | 8016 KB | Output is correct |
23 | Correct | 134 ms | 8120 KB | Output is correct |
24 | Correct | 315 ms | 150868 KB | Output is correct |
25 | Correct | 328 ms | 155168 KB | Output is correct |
26 | Correct | 325 ms | 155476 KB | Output is correct |
27 | Correct | 448 ms | 210768 KB | Output is correct |
28 | Correct | 458 ms | 210768 KB | Output is correct |
29 | Correct | 455 ms | 210772 KB | Output is correct |
30 | Correct | 459 ms | 210768 KB | Output is correct |
31 | Correct | 469 ms | 205428 KB | Output is correct |
32 | Correct | 452 ms | 210440 KB | Output is correct |
33 | Correct | 235 ms | 132436 KB | Output is correct |
34 | Correct | 225 ms | 114100 KB | Output is correct |
35 | Correct | 235 ms | 131668 KB | Output is correct |
36 | Correct | 278 ms | 171908 KB | Output is correct |
37 | Correct | 303 ms | 159624 KB | Output is correct |
38 | Correct | 285 ms | 172336 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 4952 KB | Output is correct |
2 | Correct | 1 ms | 5036 KB | Output is correct |
3 | Correct | 1 ms | 4956 KB | Output is correct |
4 | Correct | 2 ms | 4956 KB | Output is correct |
5 | Correct | 4 ms | 5468 KB | Output is correct |
6 | Correct | 3 ms | 5532 KB | Output is correct |
7 | Correct | 3 ms | 5468 KB | Output is correct |
8 | Correct | 5 ms | 7032 KB | Output is correct |
9 | Correct | 5 ms | 7000 KB | Output is correct |
10 | Correct | 6 ms | 7256 KB | Output is correct |
11 | Correct | 5 ms | 6844 KB | Output is correct |
12 | Correct | 3 ms | 6236 KB | Output is correct |
13 | Correct | 7 ms | 6748 KB | Output is correct |
14 | Correct | 4 ms | 6236 KB | Output is correct |
15 | Correct | 3 ms | 5724 KB | Output is correct |
16 | Correct | 3 ms | 6236 KB | Output is correct |
17 | Correct | 4 ms | 6232 KB | Output is correct |
18 | Correct | 3 ms | 5980 KB | Output is correct |
19 | Correct | 4 ms | 6492 KB | Output is correct |
20 | Correct | 135 ms | 7940 KB | Output is correct |
21 | Correct | 134 ms | 8016 KB | Output is correct |
22 | Correct | 130 ms | 8016 KB | Output is correct |
23 | Correct | 134 ms | 8120 KB | Output is correct |
24 | Correct | 315 ms | 150868 KB | Output is correct |
25 | Correct | 328 ms | 155168 KB | Output is correct |
26 | Correct | 325 ms | 155476 KB | Output is correct |
27 | Correct | 448 ms | 210768 KB | Output is correct |
28 | Correct | 458 ms | 210768 KB | Output is correct |
29 | Correct | 455 ms | 210772 KB | Output is correct |
30 | Correct | 459 ms | 210768 KB | Output is correct |
31 | Correct | 469 ms | 205428 KB | Output is correct |
32 | Correct | 452 ms | 210440 KB | Output is correct |
33 | Correct | 235 ms | 132436 KB | Output is correct |
34 | Correct | 225 ms | 114100 KB | Output is correct |
35 | Correct | 235 ms | 131668 KB | Output is correct |
36 | Correct | 278 ms | 171908 KB | Output is correct |
37 | Correct | 303 ms | 159624 KB | Output is correct |
38 | Correct | 285 ms | 172336 KB | Output is correct |
39 | Correct | 348 ms | 151904 KB | Output is correct |
40 | Correct | 327 ms | 155988 KB | Output is correct |
41 | Correct | 330 ms | 156688 KB | Output is correct |
42 | Correct | 370 ms | 156784 KB | Output is correct |
43 | Correct | 336 ms | 155692 KB | Output is correct |
44 | Correct | 152 ms | 10836 KB | Output is correct |
45 | Correct | 135 ms | 10168 KB | Output is correct |
46 | Correct | 136 ms | 10028 KB | Output is correct |
47 | Correct | 144 ms | 9812 KB | Output is correct |
48 | Correct | 132 ms | 9532 KB | Output is correct |
49 | Correct | 492 ms | 213856 KB | Output is correct |
50 | Correct | 465 ms | 212872 KB | Output is correct |
51 | Correct | 155 ms | 10580 KB | Output is correct |
52 | Correct | 138 ms | 9856 KB | Output is correct |
53 | Correct | 317 ms | 174940 KB | Output is correct |
54 | Correct | 358 ms | 162640 KB | Output is correct |
55 | Correct | 290 ms | 174160 KB | Output is correct |
56 | Correct | 304 ms | 162644 KB | Output is correct |
57 | Correct | 156 ms | 10836 KB | Output is correct |
58 | Correct | 155 ms | 10916 KB | Output is correct |
59 | Correct | 140 ms | 9920 KB | Output is correct |
60 | Correct | 137 ms | 9936 KB | Output is correct |
61 | Correct | 532 ms | 213080 KB | Output is correct |
62 | Correct | 326 ms | 174676 KB | Output is correct |
63 | Correct | 342 ms | 162288 KB | Output is correct |
64 | Correct | 583 ms | 213056 KB | Output is correct |
65 | Correct | 413 ms | 174160 KB | Output is correct |
66 | Correct | 450 ms | 163108 KB | Output is correct |
67 | Correct | 657 ms | 213076 KB | Output is correct |
68 | Correct | 505 ms | 174676 KB | Output is correct |
69 | Correct | 524 ms | 160992 KB | Output is correct |
70 | Correct | 468 ms | 213072 KB | Output is correct |
71 | Correct | 286 ms | 174672 KB | Output is correct |
72 | Correct | 311 ms | 162708 KB | Output is correct |
73 | Correct | 472 ms | 213072 KB | Output is correct |
74 | Correct | 306 ms | 175184 KB | Output is correct |
75 | Correct | 311 ms | 162620 KB | Output is correct |
76 | Correct | 502 ms | 214608 KB | Output is correct |
77 | Correct | 593 ms | 213772 KB | Output is correct |
78 | Correct | 458 ms | 213764 KB | Output is correct |
79 | Correct | 155 ms | 10836 KB | Output is correct |
80 | Correct | 172 ms | 10072 KB | Output is correct |
81 | Correct | 134 ms | 9556 KB | Output is correct |
82 | Correct | 531 ms | 214372 KB | Output is correct |
83 | Correct | 506 ms | 209004 KB | Output is correct |
84 | Correct | 605 ms | 213592 KB | Output is correct |
85 | Correct | 608 ms | 208136 KB | Output is correct |
86 | Correct | 469 ms | 213588 KB | Output is correct |
87 | Correct | 486 ms | 208468 KB | Output is correct |
88 | Correct | 157 ms | 10796 KB | Output is correct |
89 | Correct | 150 ms | 10792 KB | Output is correct |
90 | Correct | 169 ms | 10064 KB | Output is correct |
91 | Correct | 169 ms | 10020 KB | Output is correct |
92 | Correct | 137 ms | 9676 KB | Output is correct |
93 | Correct | 153 ms | 9500 KB | Output is correct |
94 | Correct | 273 ms | 136572 KB | Output is correct |
95 | Correct | 279 ms | 117176 KB | Output is correct |
96 | Correct | 375 ms | 134996 KB | Output is correct |
97 | Correct | 362 ms | 118352 KB | Output is correct |
98 | Correct | 251 ms | 135368 KB | Output is correct |
99 | Correct | 233 ms | 117916 KB | Output is correct |
100 | Correct | 157 ms | 10836 KB | Output is correct |
101 | Correct | 154 ms | 10832 KB | Output is correct |
102 | Correct | 172 ms | 10132 KB | Output is correct |
103 | Correct | 160 ms | 10016 KB | Output is correct |
104 | Correct | 134 ms | 9556 KB | Output is correct |
105 | Correct | 140 ms | 10052 KB | Output is correct |
106 | Correct | 312 ms | 174968 KB | Output is correct |
107 | Correct | 338 ms | 163408 KB | Output is correct |
108 | Correct | 436 ms | 175272 KB | Output is correct |
109 | Correct | 487 ms | 162624 KB | Output is correct |
110 | Correct | 295 ms | 175444 KB | Output is correct |
111 | Correct | 317 ms | 163132 KB | Output is correct |
112 | Correct | 153 ms | 10832 KB | Output is correct |
113 | Correct | 153 ms | 10828 KB | Output is correct |
114 | Correct | 165 ms | 10052 KB | Output is correct |
115 | Correct | 167 ms | 10032 KB | Output is correct |
116 | Correct | 135 ms | 9552 KB | Output is correct |
117 | Correct | 133 ms | 9512 KB | Output is correct |
118 | Correct | 480 ms | 212920 KB | Output is correct |
119 | Correct | 283 ms | 174540 KB | Output is correct |
120 | Correct | 303 ms | 161624 KB | Output is correct |
121 | Correct | 458 ms | 212624 KB | Output is correct |
122 | Correct | 285 ms | 173940 KB | Output is correct |
123 | Correct | 299 ms | 161424 KB | Output is correct |
124 | Correct | 464 ms | 213164 KB | Output is correct |
125 | Correct | 284 ms | 174840 KB | Output is correct |
126 | Correct | 305 ms | 161272 KB | Output is correct |