# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106441 | 2019-04-18T13:41:21 Z | RedNextCentury | Ball Machine (BOI13_ballmachine) | C++14 | 520 ms | 47456 KB |
#include<bits/stdc++.h> using namespace std; vector<int> adj[1000000]; int mn[1000000]; bool cmp(int a,int b) { return mn[a]<mn[b]; } void pre(int v) { mn[v]=v; for (auto u:adj[v]) { pre(u); mn[v]=min(mn[v],mn[u]); } } int pa[1000001][21]; int ord[1000001]; int tt=1; void dfs(int v) { for (auto u:adj[v]) dfs(u); ord[v]=tt++; } bool has[1000000]; int main() { freopen("out","w",stdout); ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); int n,q; cin>>n>>q; int root=-1; for (int i=1;i<=n;i++) { cin>>pa[i][0]; if (pa[i][0]==0) root = i; else adj[pa[i][0]].push_back(i); } for (int j=1;j<=18;j++) for (int i=1;i<=n;i++) pa[i][j]=pa[pa[i][j-1]][j-1]; pre(root); for (int i=1;i<=n;i++) sort(adj[i].begin(),adj[i].end(),cmp); dfs(root); set<pair<int,int> > s; for (int i=1;i<=n;i++) s.insert({ord[i],i}); while(q--) { int t,v; cin>>t>>v; if (t==1) { pair<int,int> p; while(v--) { p = *s.begin(); s.erase(s.begin()); has[p.second]=1; } cout<<p.second<<endl; } else { int u = v; int ret=0; for (int i=18;i>=0;i--) if (has[pa[u][i]]) u = pa[u][i] , ret+=(1<<i); has[u]=0; s.insert({ord[u],u}); cout<<ret<<endl; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 22 ms | 23936 KB | Output isn't correct |
2 | Incorrect | 368 ms | 35192 KB | Output isn't correct |
3 | Incorrect | 282 ms | 35384 KB | Output isn't correct |
4 | Incorrect | 24 ms | 23936 KB | Output isn't correct |
5 | Incorrect | 29 ms | 23928 KB | Output isn't correct |
6 | Incorrect | 25 ms | 24064 KB | Output isn't correct |
7 | Incorrect | 26 ms | 24056 KB | Output isn't correct |
8 | Incorrect | 27 ms | 24064 KB | Output isn't correct |
9 | Incorrect | 44 ms | 24576 KB | Output isn't correct |
10 | Incorrect | 105 ms | 26804 KB | Output isn't correct |
11 | Incorrect | 388 ms | 35192 KB | Output isn't correct |
12 | Incorrect | 272 ms | 35192 KB | Output isn't correct |
13 | Incorrect | 379 ms | 35432 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 179 ms | 28660 KB | Output isn't correct |
2 | Incorrect | 446 ms | 43480 KB | Output isn't correct |
3 | Incorrect | 288 ms | 40048 KB | Output isn't correct |
4 | Incorrect | 252 ms | 30488 KB | Output isn't correct |
5 | Incorrect | 247 ms | 30328 KB | Output isn't correct |
6 | Incorrect | 214 ms | 30200 KB | Output isn't correct |
7 | Incorrect | 240 ms | 29600 KB | Output isn't correct |
8 | Incorrect | 178 ms | 28536 KB | Output isn't correct |
9 | Incorrect | 413 ms | 44148 KB | Output isn't correct |
10 | Incorrect | 434 ms | 43488 KB | Output isn't correct |
11 | Incorrect | 401 ms | 43512 KB | Output isn't correct |
12 | Incorrect | 477 ms | 41848 KB | Output isn't correct |
13 | Incorrect | 347 ms | 44452 KB | Output isn't correct |
14 | Incorrect | 295 ms | 40052 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 244 ms | 34136 KB | Output isn't correct |
2 | Incorrect | 520 ms | 42488 KB | Output isn't correct |
3 | Incorrect | 339 ms | 42672 KB | Output isn't correct |
4 | Incorrect | 301 ms | 39800 KB | Output isn't correct |
5 | Incorrect | 369 ms | 39620 KB | Output isn't correct |
6 | Incorrect | 356 ms | 39544 KB | Output isn't correct |
7 | Incorrect | 330 ms | 38648 KB | Output isn't correct |
8 | Incorrect | 303 ms | 42448 KB | Output isn't correct |
9 | Incorrect | 516 ms | 44280 KB | Output isn't correct |
10 | Incorrect | 470 ms | 43640 KB | Output isn't correct |
11 | Incorrect | 505 ms | 43768 KB | Output isn't correct |
12 | Incorrect | 503 ms | 42616 KB | Output isn't correct |
13 | Incorrect | 501 ms | 47456 KB | Output isn't correct |
14 | Incorrect | 480 ms | 40828 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 463 ms | 44224 KB | Output isn't correct |
2 | Incorrect | 480 ms | 42504 KB | Output isn't correct |
3 | Incorrect | 358 ms | 46968 KB | Output isn't correct |
4 | Incorrect | 473 ms | 44308 KB | Output isn't correct |
5 | Incorrect | 460 ms | 43768 KB | Output isn't correct |
6 | Incorrect | 419 ms | 43704 KB | Output isn't correct |
7 | Incorrect | 486 ms | 42844 KB | Output isn't correct |
8 | Incorrect | 367 ms | 46968 KB | Output isn't correct |
9 | Incorrect | 338 ms | 40180 KB | Output isn't correct |