# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
26658 | 2017-07-04T13:28:30 Z | kdh9949 | Ball Machine (BOI13_ballmachine) | C++14 | 299 ms | 33208 KB |
#include <bits/stdc++.h> using namespace std; struct Nod{ int p, x; bool operator<(const Nod &oth) const { return p > oth.p; } }; priority_queue<Nod> pq; int n, q, r, mn[100010], pn[100010], cnt, c[100010], sp[17][100010]; vector<int> ch[100010], nc[100010]; int g(int x){ priority_queue<Nod> pq; for(auto &i : ch[x]){ pq.push({g(i), i}); } int ret = x; for(; !pq.empty(); pq.pop()){ nc[x].push_back(pq.top().x); ret = min(ret, pq.top().p); } return ret; } void f(int x){ for(int i = 1; i < 17; i++) sp[i][x] = sp[i - 1][sp[i - 1][x]]; for(auto &i : nc[x]) f(i); pn[x] = ++cnt; pq.push({pn[x], x}); } int main(){ scanf("%d%d", &n, &q); for(int i = 1; i <= n; i++){ scanf("%d", sp[0] + i); if(!sp[0][i]) r = i; else ch[sp[0][i]].push_back(i); } g(r); f(r); for(int t, x, ans; q--; ){ scanf("%d%d", &t, &x); if(t == 1){ while(x--){ ans = pq.top().x; c[pq.top().x] = 1; pq.pop(); } printf("%d\n", ans); } else{ ans = 0; for(int i = 16; i >= 0; i--){ if(c[sp[i][x]]){ ans += (1 << i); x = sp[i][x]; } } c[x] = 0; pq.push({pn[x], x}); printf("%d\n", ans); } } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 3 ms | 14524 KB | Output is correct |
2 | Correct | 143 ms | 17424 KB | Output is correct |
3 | Correct | 76 ms | 17424 KB | Output is correct |
4 | Correct | 0 ms | 14524 KB | Output is correct |
5 | Correct | 0 ms | 14524 KB | Output is correct |
6 | Correct | 0 ms | 14524 KB | Output is correct |
7 | Correct | 0 ms | 14524 KB | Output is correct |
8 | Correct | 3 ms | 14524 KB | Output is correct |
9 | Correct | 6 ms | 14792 KB | Output is correct |
10 | Correct | 33 ms | 15240 KB | Output is correct |
11 | Correct | 173 ms | 17424 KB | Output is correct |
12 | Correct | 103 ms | 17424 KB | Output is correct |
13 | Correct | 126 ms | 17424 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 18000 KB | Output is correct |
2 | Correct | 253 ms | 25392 KB | Output is correct |
3 | Correct | 133 ms | 19248 KB | Output is correct |
4 | Correct | 79 ms | 17932 KB | Output is correct |
5 | Correct | 89 ms | 17672 KB | Output is correct |
6 | Correct | 69 ms | 17676 KB | Output is correct |
7 | Correct | 76 ms | 16704 KB | Output is correct |
8 | Correct | 46 ms | 18004 KB | Output is correct |
9 | Correct | 236 ms | 26232 KB | Output is correct |
10 | Correct | 263 ms | 25396 KB | Output is correct |
11 | Correct | 216 ms | 25392 KB | Output is correct |
12 | Correct | 236 ms | 22508 KB | Output is correct |
13 | Correct | 156 ms | 31188 KB | Output is correct |
14 | Correct | 133 ms | 19248 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 96 ms | 20356 KB | Output is correct |
2 | Correct | 276 ms | 22668 KB | Output is correct |
3 | Correct | 209 ms | 29772 KB | Output is correct |
4 | Correct | 199 ms | 24200 KB | Output is correct |
5 | Correct | 99 ms | 23524 KB | Output is correct |
6 | Correct | 219 ms | 23528 KB | Output is correct |
7 | Correct | 173 ms | 21344 KB | Output is correct |
8 | Correct | 206 ms | 29772 KB | Output is correct |
9 | Correct | 263 ms | 26232 KB | Output is correct |
10 | Correct | 273 ms | 25412 KB | Output is correct |
11 | Correct | 286 ms | 25404 KB | Output is correct |
12 | Correct | 263 ms | 22664 KB | Output is correct |
13 | Correct | 299 ms | 33208 KB | Output is correct |
14 | Correct | 186 ms | 19256 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 289 ms | 26228 KB | Output is correct |
2 | Correct | 273 ms | 22668 KB | Output is correct |
3 | Correct | 176 ms | 33204 KB | Output is correct |
4 | Correct | 299 ms | 26232 KB | Output is correct |
5 | Correct | 269 ms | 25404 KB | Output is correct |
6 | Correct | 249 ms | 25404 KB | Output is correct |
7 | Correct | 286 ms | 22668 KB | Output is correct |
8 | Correct | 206 ms | 33208 KB | Output is correct |
9 | Correct | 136 ms | 19256 KB | Output is correct |