# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
30897 | 2017-07-31T12:57:49 Z | Navick | Ball Machine (BOI13_ballmachine) | C++14 | 429 ms | 28152 KB |
#include <bits/stdc++.h> #define F first #define S second #define pii pair<int, int> #define pb push_back using namespace std; typedef long long ll; typedef long double ld; const int N = 1e5 + 10, LOG = 18; bool full[N]; vector<int> adj[N]; int n, root, g[N], mn[N], par[N][LOG], ord[N], turn = 0; set<pii> st; bool cmp(int u, int v){ return mn[u] < mn[v]; } bool pmc(int u, int v){ return ord[u] < ord[v]; } void p_dfs(int v, int p = 0){ par[v][0] = p; for(int i=1; i<LOG; i++) par[v][i] = par[par[v][i - 1]][i - 1]; mn[v] = v; for(auto u : adj[v]){ p_dfs(u, v); mn[v] = min(mn[v], mn[u]); } sort(adj[v].begin(), adj[v].end(), cmp); } void dfs(int v){ for(auto u : adj[v]) dfs(u); ord[v] = turn++; } int add(){ int v = (*st.begin()).S; st.erase(st.begin()); full[v] = true; return v; } int erase(int v){ int ans = 0; for(int i=LOG-1; i>=0; i--){ if(full[par[v][i]]){ ans += (1 << i); v = par[v][i]; } } full[v] = false; st.insert({ord[v], v}); return ans; } int main(){ //ios_base::sync_with_stdio(0); cin.tie(0); int q; scanf("%d %d", &n, &q); for(int i=1; i<=n; i++){ int p; scanf("%d", &p); if(p == 0)root = i; else adj[p].pb(i); } p_dfs(root); dfs(root); for(int i=0; i<n; i++) g[i] = i + 1; sort(g, g + n, pmc); for(int i=1; i<=n; i++) st.insert({ord[i], i}); while(q--){ int tp; scanf("%d", &tp); if(tp == 1){ int k, pos = -1; scanf("%d", &k); while(k--) pos = add(); printf("%d\n", pos); }else{ int v; scanf("%d", &v); printf("%d\n", erase(v)); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 12672 KB | Output is correct |
2 | Correct | 233 ms | 16764 KB | Output is correct |
3 | Correct | 116 ms | 16764 KB | Output is correct |
4 | Correct | 0 ms | 12672 KB | Output is correct |
5 | Correct | 0 ms | 12672 KB | Output is correct |
6 | Correct | 0 ms | 12804 KB | Output is correct |
7 | Correct | 3 ms | 12804 KB | Output is correct |
8 | Correct | 0 ms | 12804 KB | Output is correct |
9 | Correct | 13 ms | 12936 KB | Output is correct |
10 | Correct | 36 ms | 13728 KB | Output is correct |
11 | Correct | 246 ms | 16764 KB | Output is correct |
12 | Correct | 153 ms | 16764 KB | Output is correct |
13 | Correct | 196 ms | 16764 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 69 ms | 15428 KB | Output is correct |
2 | Correct | 346 ms | 23044 KB | Output is correct |
3 | Correct | 146 ms | 18768 KB | Output is correct |
4 | Correct | 96 ms | 15832 KB | Output is correct |
5 | Correct | 83 ms | 15696 KB | Output is correct |
6 | Correct | 79 ms | 15696 KB | Output is correct |
7 | Correct | 76 ms | 14932 KB | Output is correct |
8 | Correct | 56 ms | 15424 KB | Output is correct |
9 | Correct | 323 ms | 23584 KB | Output is correct |
10 | Correct | 229 ms | 23048 KB | Output is correct |
11 | Correct | 333 ms | 23048 KB | Output is correct |
12 | Correct | 296 ms | 20924 KB | Output is correct |
13 | Correct | 226 ms | 26304 KB | Output is correct |
14 | Correct | 189 ms | 18768 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 179 ms | 18064 KB | Output is correct |
2 | Correct | 363 ms | 21100 KB | Output is correct |
3 | Correct | 269 ms | 25000 KB | Output is correct |
4 | Correct | 266 ms | 21344 KB | Output is correct |
5 | Correct | 306 ms | 20952 KB | Output is correct |
6 | Correct | 256 ms | 20948 KB | Output is correct |
7 | Correct | 289 ms | 19392 KB | Output is correct |
8 | Correct | 256 ms | 25000 KB | Output is correct |
9 | Correct | 376 ms | 23576 KB | Output is correct |
10 | Correct | 359 ms | 23052 KB | Output is correct |
11 | Correct | 406 ms | 23052 KB | Output is correct |
12 | Correct | 386 ms | 21100 KB | Output is correct |
13 | Correct | 369 ms | 28148 KB | Output is correct |
14 | Correct | 306 ms | 18756 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 303 ms | 23580 KB | Output is correct |
2 | Correct | 279 ms | 21100 KB | Output is correct |
3 | Correct | 166 ms | 28148 KB | Output is correct |
4 | Correct | 396 ms | 23580 KB | Output is correct |
5 | Correct | 383 ms | 23052 KB | Output is correct |
6 | Correct | 306 ms | 23056 KB | Output is correct |
7 | Correct | 429 ms | 21100 KB | Output is correct |
8 | Correct | 216 ms | 28152 KB | Output is correct |
9 | Correct | 156 ms | 18760 KB | Output is correct |