# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
78986 | 2018-10-10T06:14:49 Z | win11905 | Ball Machine (BOI13_ballmachine) | C++11 | 155 ms | 28348 KB |
#include <bits/stdc++.h> using namespace std; #define pii pair<int, int> #define x first #define y second const int N = 1e5+5; int n, m; int par[N][17], dep[N]; vector<int> g[N]; vector<pii> ng[N]; int dfs(int u) { int mn = u; for(int i = 1; i < 17; ++i) par[u][i] = par[par[u][i-1]][i-1]; for(int v : g[u]) { dep[v] = dep[u] + 1, par[v][0] = u; int now = dfs(v); mn = min(mn, now); ng[u].emplace_back(mn, v); } sort(ng[u].begin(), ng[u].end()); return mn; } int A[N], ptr; int pos[N]; int block = 320; int sz[350]; bool d[N]; pii t[350]; void solve(int u) { for(auto v : ng[u]) solve(v.y); A[ptr++] = u; } int main() { scanf("%d %d", &n, &m); for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i); dep[1] = 1, dfs(1); solve(1); for(int i = 0; i < n; ++i) sz[i/block]++; int last = n / block; for(int i = 1; i <= n; ++i) pos[A[i]] = i; for(int i = 0, a, b; i < m; ++i) { scanf("%d %d", &a, &b); if(a == 1) { for(int i = 0; i <= last; ++i) { if(b - (sz[i] - t[i].x) > 0) b -= sz[i] - t[i].x, t[i] = pii(sz[i], 1); else { assert(t[i].y == 0); t[i] = pii(0, 0); for(int j = i * block; j < i * block + sz[i]; ++j) { if(d[j]) t[i].x++; else if(b--) d[j] = true, t[i].x++; if(!b) { printf("%d\n", A[j]); break; } } break; } } } else { auto check = [&](int v) { if(t[pos[v]/block].y) return true; else if(d[pos[v]]) return true; }; int sum = 0; for(int i = 16; ~i; --i) if(check(par[b][i])) b = par[b][i], sum += 1<<i; printf("%d\n", sum); b = pos[b]; int ith = b / block; if(t[ith].y) for(int j = ith * block; j < ith * block + sz[ith]; ++j) d[j] = 1; d[b] = 0; t[ith] = pii(0, 0); for(int j = ith * block; j < ith * block + sz[ith]; ++j) t[ith].x += d[j]; } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 6 ms | 4984 KB | Output isn't correct |
2 | Incorrect | 79 ms | 6900 KB | Output isn't correct |
3 | Incorrect | 91 ms | 6900 KB | Output isn't correct |
4 | Incorrect | 5 ms | 6900 KB | Output isn't correct |
5 | Incorrect | 6 ms | 6900 KB | Output isn't correct |
6 | Incorrect | 6 ms | 6900 KB | Output isn't correct |
7 | Incorrect | 6 ms | 6900 KB | Output isn't correct |
8 | Incorrect | 6 ms | 6900 KB | Output isn't correct |
9 | Incorrect | 11 ms | 6900 KB | Output isn't correct |
10 | Incorrect | 19 ms | 6900 KB | Output isn't correct |
11 | Incorrect | 80 ms | 7248 KB | Output isn't correct |
12 | Incorrect | 91 ms | 7248 KB | Output isn't correct |
13 | Incorrect | 80 ms | 7248 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 57 ms | 10284 KB | Output isn't correct |
2 | Incorrect | 101 ms | 18656 KB | Output isn't correct |
3 | Incorrect | 93 ms | 18656 KB | Output isn't correct |
4 | Incorrect | 62 ms | 18656 KB | Output isn't correct |
5 | Incorrect | 52 ms | 18656 KB | Output isn't correct |
6 | Incorrect | 55 ms | 18656 KB | Output isn't correct |
7 | Incorrect | 52 ms | 18656 KB | Output isn't correct |
8 | Incorrect | 60 ms | 18656 KB | Output isn't correct |
9 | Incorrect | 127 ms | 23916 KB | Output isn't correct |
10 | Incorrect | 105 ms | 23916 KB | Output isn't correct |
11 | Incorrect | 81 ms | 23916 KB | Output isn't correct |
12 | Incorrect | 86 ms | 23916 KB | Output isn't correct |
13 | Incorrect | 124 ms | 23916 KB | Output isn't correct |
14 | Incorrect | 91 ms | 23916 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 54 ms | 23916 KB | Output isn't correct |
2 | Incorrect | 116 ms | 23916 KB | Output isn't correct |
3 | Incorrect | 74 ms | 23916 KB | Output isn't correct |
4 | Incorrect | 54 ms | 23916 KB | Output isn't correct |
5 | Incorrect | 53 ms | 23916 KB | Output isn't correct |
6 | Incorrect | 57 ms | 23916 KB | Output isn't correct |
7 | Incorrect | 72 ms | 23916 KB | Output isn't correct |
8 | Incorrect | 73 ms | 23916 KB | Output isn't correct |
9 | Incorrect | 87 ms | 23916 KB | Output isn't correct |
10 | Incorrect | 115 ms | 23916 KB | Output isn't correct |
11 | Incorrect | 105 ms | 23916 KB | Output isn't correct |
12 | Incorrect | 118 ms | 23916 KB | Output isn't correct |
13 | Incorrect | 113 ms | 23916 KB | Output isn't correct |
14 | Incorrect | 91 ms | 23916 KB | Output isn't correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 87 ms | 23916 KB | Output isn't correct |
2 | Incorrect | 133 ms | 23916 KB | Output isn't correct |
3 | Incorrect | 155 ms | 28348 KB | Output isn't correct |
4 | Incorrect | 91 ms | 28348 KB | Output isn't correct |
5 | Incorrect | 92 ms | 28348 KB | Output isn't correct |
6 | Incorrect | 141 ms | 28348 KB | Output isn't correct |
7 | Incorrect | 126 ms | 28348 KB | Output isn't correct |
8 | Incorrect | 149 ms | 28348 KB | Output isn't correct |
9 | Incorrect | 100 ms | 28348 KB | Output isn't correct |