# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106306 | 2019-04-17T20:38:45 Z | Pajaraja | Ball Machine (BOI13_ballmachine) | C++17 | 278 ms | 27784 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() (int a,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 | 2816 KB | Output is correct |
2 | Correct | 119 ms | 11388 KB | Output is correct |
3 | Correct | 71 ms | 11256 KB | Output is correct |
4 | Correct | 4 ms | 2816 KB | Output is correct |
5 | Correct | 5 ms | 2944 KB | Output is correct |
6 | Correct | 4 ms | 2944 KB | Output is correct |
7 | Correct | 5 ms | 2892 KB | Output is correct |
8 | Correct | 5 ms | 2944 KB | Output is correct |
9 | Correct | 12 ms | 3360 KB | Output is correct |
10 | Correct | 23 ms | 4864 KB | Output is correct |
11 | Correct | 120 ms | 11256 KB | Output is correct |
12 | Correct | 77 ms | 11160 KB | Output is correct |
13 | Correct | 96 ms | 11384 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 7616 KB | Output is correct |
2 | Correct | 183 ms | 20344 KB | Output is correct |
3 | Correct | 96 ms | 14820 KB | Output is correct |
4 | Correct | 101 ms | 8768 KB | Output is correct |
5 | Correct | 63 ms | 8700 KB | Output is correct |
6 | Correct | 60 ms | 8704 KB | Output is correct |
7 | Correct | 70 ms | 7564 KB | Output is correct |
8 | Correct | 44 ms | 7596 KB | Output is correct |
9 | Correct | 210 ms | 20600 KB | Output is correct |
10 | Correct | 208 ms | 20344 KB | Output is correct |
11 | Correct | 160 ms | 20344 KB | Output is correct |
12 | Correct | 253 ms | 17500 KB | Output is correct |
13 | Correct | 130 ms | 24952 KB | Output is correct |
14 | Correct | 124 ms | 14700 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 70 ms | 11896 KB | Output is correct |
2 | Correct | 184 ms | 17940 KB | Output is correct |
3 | Correct | 157 ms | 22860 KB | Output is correct |
4 | Correct | 164 ms | 17144 KB | Output is correct |
5 | Correct | 130 ms | 16892 KB | Output is correct |
6 | Correct | 121 ms | 17016 KB | Output is correct |
7 | Correct | 180 ms | 14796 KB | Output is correct |
8 | Correct | 237 ms | 22776 KB | Output is correct |
9 | Correct | 237 ms | 20764 KB | Output is correct |
10 | Correct | 240 ms | 20344 KB | Output is correct |
11 | Correct | 193 ms | 20344 KB | Output is correct |
12 | Correct | 178 ms | 17920 KB | Output is correct |
13 | Correct | 278 ms | 27784 KB | Output is correct |
14 | Correct | 158 ms | 15208 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 250 ms | 20892 KB | Output is correct |
2 | Correct | 219 ms | 17856 KB | Output is correct |
3 | Correct | 226 ms | 27768 KB | Output is correct |
4 | Correct | 263 ms | 21112 KB | Output is correct |
5 | Correct | 232 ms | 20344 KB | Output is correct |
6 | Correct | 184 ms | 20344 KB | Output is correct |
7 | Correct | 244 ms | 18052 KB | Output is correct |
8 | Correct | 184 ms | 27724 KB | Output is correct |
9 | Correct | 125 ms | 14760 KB | Output is correct |