# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
91715 | 2018-12-29T12:56:24 Z | Mercenary | Ball Machine (BOI13_ballmachine) | C++14 | 189 ms | 24272 KB |
#include<bits/stdc++.h> using namespace std; #define taskname "TEST" #define pb push_back typedef long double ld; typedef long long ll; const int maxn = 1e5 + 5; const int logn = log2(maxn) + 1; int n , q , root; vector<int> adj[maxn]; int P[maxn][logn]; int dp[maxn] , id[maxn] , id1[maxn]; void enter() { cin >> n >> q; for(int i = 1 ; i <= n ; ++i) { int u;cin >> u; if(u == 0)root = i; else adj[u].pb(i) , P[i][0] = u; } } void DFS(int u) { dp[u] = u; for(int c : adj[u]) DFS(c) , dp[u] = min(dp[u] , dp[c]); } void Priority(int u) { static int nTime = 0; sort(adj[u].begin(),adj[u].end(),[](const int x , const int y){ return dp[x] < dp[y]; }); for(int c : adj[u]) Priority(c); id[u] = ++nTime;id1[nTime] = u; } priority_queue<int,vector<int>,greater<int>> pq; int vis[maxn]; void solve() { for(int i = 1 ; i < logn ; ++i) for(int j = 1 ; j <= n ; ++j) P[j][i] = P[P[j][i - 1]][i - 1]; for(int i = 1 ; i <= n ; ++i)pq.push(i); while(q--) { int key;cin >> key; if(key == 1) { int k;cin >> k; int last; while(k--) { last = id1[pq.top()]; vis[last] = 1; pq.pop(); } cout << last << '\n'; } else { int u;cin >> u;int res = 0; for(int i = logn - 1 ; i >= 0 ; --i) if(vis[P[u][i]])u = P[u][i] , res += (1 << i); pq.push(id[u]);vis[u] = 0; cout << res << '\n'; } } } int main() { ios_base::sync_with_stdio(0); cin.tie(0); if(fopen(taskname".INP","r")) freopen(taskname".INP", "r",stdin) , freopen(taskname".OUT", "w",stdout); enter(); DFS(root);Priority(root);solve(); }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2680 KB | Output is correct |
2 | Correct | 78 ms | 10868 KB | Output is correct |
3 | Correct | 59 ms | 10572 KB | Output is correct |
4 | Correct | 3 ms | 2740 KB | Output is correct |
5 | Correct | 3 ms | 2680 KB | Output is correct |
6 | Correct | 4 ms | 2808 KB | Output is correct |
7 | Correct | 4 ms | 2808 KB | Output is correct |
8 | Correct | 5 ms | 2808 KB | Output is correct |
9 | Correct | 8 ms | 3320 KB | Output is correct |
10 | Correct | 18 ms | 4732 KB | Output is correct |
11 | Correct | 78 ms | 10892 KB | Output is correct |
12 | Correct | 56 ms | 10612 KB | Output is correct |
13 | Correct | 74 ms | 10868 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 32 ms | 7164 KB | Output is correct |
2 | Correct | 119 ms | 18804 KB | Output is correct |
3 | Correct | 64 ms | 13680 KB | Output is correct |
4 | Correct | 47 ms | 8232 KB | Output is correct |
5 | Correct | 48 ms | 8184 KB | Output is correct |
6 | Correct | 47 ms | 8184 KB | Output is correct |
7 | Correct | 47 ms | 7288 KB | Output is correct |
8 | Correct | 32 ms | 7160 KB | Output is correct |
9 | Correct | 127 ms | 19312 KB | Output is correct |
10 | Correct | 115 ms | 18804 KB | Output is correct |
11 | Correct | 116 ms | 18848 KB | Output is correct |
12 | Correct | 109 ms | 16612 KB | Output is correct |
13 | Correct | 110 ms | 21364 KB | Output is correct |
14 | Correct | 73 ms | 13784 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 56 ms | 11128 KB | Output is correct |
2 | Correct | 151 ms | 17144 KB | Output is correct |
3 | Correct | 92 ms | 19828 KB | Output is correct |
4 | Correct | 79 ms | 15984 KB | Output is correct |
5 | Correct | 83 ms | 15604 KB | Output is correct |
6 | Correct | 86 ms | 15604 KB | Output is correct |
7 | Correct | 75 ms | 14056 KB | Output is correct |
8 | Correct | 104 ms | 19800 KB | Output is correct |
9 | Correct | 123 ms | 19460 KB | Output is correct |
10 | Correct | 120 ms | 19060 KB | Output is correct |
11 | Correct | 122 ms | 19032 KB | Output is correct |
12 | Correct | 128 ms | 17208 KB | Output is correct |
13 | Correct | 189 ms | 24272 KB | Output is correct |
14 | Correct | 113 ms | 14448 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 153 ms | 19588 KB | Output is correct |
2 | Correct | 115 ms | 16980 KB | Output is correct |
3 | Correct | 121 ms | 23584 KB | Output is correct |
4 | Correct | 142 ms | 19572 KB | Output is correct |
5 | Correct | 136 ms | 19100 KB | Output is correct |
6 | Correct | 117 ms | 19060 KB | Output is correct |
7 | Correct | 129 ms | 17000 KB | Output is correct |
8 | Correct | 118 ms | 23660 KB | Output is correct |
9 | Correct | 67 ms | 13680 KB | Output is correct |