# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
79023 | 2018-10-10T13:38:17 Z | win11905 | Ball Machine (BOI13_ballmachine) | C++11 | 578 ms | 29000 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]; int mnpth[N]; vector<int> g[N]; int dfs(int u) { mnpth[u] = 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; mnpth[u] = min(mnpth[u], dfs(v)); } return mnpth[u]; } int A[N], ptr; int pos[N]; void solve(int u) { vector<pii> ret; for(auto v : g[u]) ret.emplace_back(mnpth[v], v); sort(ret.begin(), ret.end()); for(auto v : ret) solve(v.y); A[++ptr] = u; } set<int> S; int main() { scanf("%d %d", &n, &m); for(int i = 1, val; i <= n; ++i) scanf("%d", &val), g[val].emplace_back(i); int rt = g[0][0]; dep[rt] = 1, dfs(rt); solve(rt); for(int i = 1; i <= n; ++i) pos[A[i]] = i; int ptr = 0; for(int i = 1; i <= n; ++i) S.emplace(i); for(int i = 0, a, b; i < m; ++i) { scanf("%d %d", &a, &b); if(a == 1) { while(b--) { if(!b) printf("%d\n", A[*S.begin()]); S.erase(S.begin()); } } else { int sum = 0; for(int i = 16; ~i; --i) if(par[b][i] != 0 && S.count(pos[par[b][i]]) == 0) b = par[b][i], sum += 1<<i; S.emplace(pos[b]); printf("%d\n", sum); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2808 KB | Output is correct |
2 | Correct | 214 ms | 12448 KB | Output is correct |
3 | Correct | 99 ms | 12600 KB | Output is correct |
4 | Correct | 4 ms | 12600 KB | Output is correct |
5 | Correct | 4 ms | 12600 KB | Output is correct |
6 | Correct | 6 ms | 12600 KB | Output is correct |
7 | Correct | 5 ms | 12600 KB | Output is correct |
8 | Correct | 6 ms | 12600 KB | Output is correct |
9 | Correct | 14 ms | 12600 KB | Output is correct |
10 | Correct | 40 ms | 12600 KB | Output is correct |
11 | Correct | 196 ms | 12612 KB | Output is correct |
12 | Correct | 95 ms | 12868 KB | Output is correct |
13 | Correct | 165 ms | 12868 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 60 ms | 12868 KB | Output is correct |
2 | Correct | 439 ms | 22796 KB | Output is correct |
3 | Correct | 166 ms | 22796 KB | Output is correct |
4 | Correct | 153 ms | 22796 KB | Output is correct |
5 | Correct | 233 ms | 22796 KB | Output is correct |
6 | Correct | 206 ms | 22796 KB | Output is correct |
7 | Correct | 194 ms | 22796 KB | Output is correct |
8 | Correct | 61 ms | 22796 KB | Output is correct |
9 | Correct | 368 ms | 23176 KB | Output is correct |
10 | Correct | 460 ms | 23176 KB | Output is correct |
11 | Correct | 372 ms | 23176 KB | Output is correct |
12 | Correct | 388 ms | 23176 KB | Output is correct |
13 | Correct | 197 ms | 25788 KB | Output is correct |
14 | Correct | 133 ms | 25788 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 133 ms | 25788 KB | Output is correct |
2 | Correct | 467 ms | 25788 KB | Output is correct |
3 | Correct | 362 ms | 25788 KB | Output is correct |
4 | Correct | 227 ms | 25788 KB | Output is correct |
5 | Correct | 304 ms | 25788 KB | Output is correct |
6 | Correct | 289 ms | 25788 KB | Output is correct |
7 | Correct | 296 ms | 25788 KB | Output is correct |
8 | Correct | 371 ms | 25788 KB | Output is correct |
9 | Correct | 362 ms | 25788 KB | Output is correct |
10 | Correct | 471 ms | 25788 KB | Output is correct |
11 | Correct | 478 ms | 25788 KB | Output is correct |
12 | Correct | 470 ms | 25788 KB | Output is correct |
13 | Correct | 578 ms | 29000 KB | Output is correct |
14 | Correct | 209 ms | 29000 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 367 ms | 29000 KB | Output is correct |
2 | Correct | 457 ms | 29000 KB | Output is correct |
3 | Correct | 242 ms | 29000 KB | Output is correct |
4 | Correct | 398 ms | 29000 KB | Output is correct |
5 | Correct | 553 ms | 29000 KB | Output is correct |
6 | Correct | 408 ms | 29000 KB | Output is correct |
7 | Correct | 468 ms | 29000 KB | Output is correct |
8 | Correct | 242 ms | 29000 KB | Output is correct |
9 | Correct | 126 ms | 29000 KB | Output is correct |