# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
48431 | 2018-05-13T10:07:16 Z | Pajaraja | Ball Machine (BOI13_ballmachine) | C++17 | 264 ms | 27184 KB |
#include<bits/stdc++.h> using namespace std; int pr[100007],p[20][100007],dd[100007],cnt; bool bl[100007]; vector<int> g[100007]; struct comp {bool operator() (const int& a,const int& b) {return pr[a]>pr[b];}}; priority_queue<int,vector<int>,comp> pq; void dfscalc(int s) { dd[s]=s; for(int i=0;i<g[s].size();i++) dfscalc(g[s][i]); for(int i=0;i<g[s].size();i++) dd[s]=min(dd[s],dd[g[s][i]]); } int dfs(int s) { priority_queue<pair<int,int> > ord; for(int i=0;i<g[s].size();i++) ord.push(make_pair(-dd[g[s][i]],g[s][i])); while(!ord.empty()) { dfs(ord.top().second); ord.pop(); } pr[s]=cnt++; } int main() { int n,q,root; scanf("%d%d",&n,&q); for(int i=1;i<=n;i++) { int t; scanf("%d",&t); if(t!=0) g[t].push_back(i); else root=i; p[0][i]=t; } for(int i=1;i<20;i++) for(int j=1;j<=n;j++) p[i][j]=p[i-1][p[i-1][j]]; dfscalc(root); dfs(root); for(int i=1;i<=n;i++) pq.push(i); while(q--) { int t,a,tmp=0; scanf("%d%d",&t,&a); if(t==1) { while(a--) { tmp=pq.top(); bl[tmp]=true; pq.pop(); } } else { for(int i=19;i>=0;i--) if(bl[p[i][a]]) { a=p[i][a]; tmp+=(1<<i); } bl[a]=false; pq.push(a); } printf("%d\n",tmp); } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | Output is correct |
2 | Correct | 116 ms | 10172 KB | Output is correct |
3 | Correct | 73 ms | 10296 KB | Output is correct |
4 | Correct | 4 ms | 10296 KB | Output is correct |
5 | Correct | 4 ms | 10296 KB | Output is correct |
6 | Correct | 4 ms | 10296 KB | Output is correct |
7 | Correct | 4 ms | 10296 KB | Output is correct |
8 | Correct | 5 ms | 10296 KB | Output is correct |
9 | Correct | 9 ms | 10296 KB | Output is correct |
10 | Correct | 23 ms | 10296 KB | Output is correct |
11 | Correct | 112 ms | 10324 KB | Output is correct |
12 | Correct | 76 ms | 10452 KB | Output is correct |
13 | Correct | 101 ms | 10452 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 47 ms | 10452 KB | Output is correct |
2 | Correct | 210 ms | 19872 KB | Output is correct |
3 | Correct | 89 ms | 19872 KB | Output is correct |
4 | Correct | 71 ms | 19872 KB | Output is correct |
5 | Correct | 69 ms | 19872 KB | Output is correct |
6 | Correct | 64 ms | 19872 KB | Output is correct |
7 | Correct | 66 ms | 19872 KB | Output is correct |
8 | Correct | 46 ms | 19872 KB | Output is correct |
9 | Correct | 158 ms | 20120 KB | Output is correct |
10 | Correct | 174 ms | 20120 KB | Output is correct |
11 | Correct | 150 ms | 20120 KB | Output is correct |
12 | Correct | 157 ms | 20120 KB | Output is correct |
13 | Correct | 124 ms | 24492 KB | Output is correct |
14 | Correct | 85 ms | 24492 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 79 ms | 24492 KB | Output is correct |
2 | Correct | 176 ms | 24492 KB | Output is correct |
3 | Correct | 144 ms | 24492 KB | Output is correct |
4 | Correct | 127 ms | 24492 KB | Output is correct |
5 | Correct | 114 ms | 24492 KB | Output is correct |
6 | Correct | 112 ms | 24492 KB | Output is correct |
7 | Correct | 112 ms | 24492 KB | Output is correct |
8 | Correct | 141 ms | 24492 KB | Output is correct |
9 | Correct | 173 ms | 24492 KB | Output is correct |
10 | Correct | 177 ms | 24492 KB | Output is correct |
11 | Correct | 177 ms | 24492 KB | Output is correct |
12 | Correct | 212 ms | 24492 KB | Output is correct |
13 | Correct | 264 ms | 27184 KB | Output is correct |
14 | Correct | 145 ms | 27184 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 239 ms | 27184 KB | Output is correct |
2 | Correct | 205 ms | 27184 KB | Output is correct |
3 | Correct | 144 ms | 27184 KB | Output is correct |
4 | Correct | 247 ms | 27184 KB | Output is correct |
5 | Correct | 242 ms | 27184 KB | Output is correct |
6 | Correct | 174 ms | 27184 KB | Output is correct |
7 | Correct | 254 ms | 27184 KB | Output is correct |
8 | Correct | 164 ms | 27184 KB | Output is correct |
9 | Correct | 116 ms | 27184 KB | Output is correct |