# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
575311 | 2022-06-10T07:23:56 Z | ktkerem | Ball Machine (BOI13_ballmachine) | C++17 | 176 ms | 22328 KB |
#include <cstdio> #include <vector> #include <iostream> #include <algorithm> #include <set> #include <queue> #include <utility> using namespace std; // full solution // (author: simon buerger) void readTree(int n, vector<int>& nodes) { nodes.resize(n); for(int i = 0; i < n; ++i) { scanf("%d", &nodes[i]); nodes[i]--; if(nodes[i] == -1) nodes[i] = i; } } #define LOGN 17 // will work for n <= 100.000 int n, q; vector<int> par[LOGN]; vector<vector<int> > g; vector<int> low; vector<int> post; vector<bool> ball; vector<int> layer; // root is at 0 int root; bool cmpLow(int a, int b) { return low[a] < low[b]; } bool cmpPostInv(int a, int b) { return post[a] > post[b]; } priority_queue<int, vector<int>, bool(*)(int,int)> pepsi(cmpPostInv); vector<int> full; // not ordered in any sense void dfsLow(int v) { if(v == root) layer[v] = 0; else layer[v] = 1 + layer[par[0][v]]; low[v] = v; for(int i = 0; i < (int)g[v].size(); ++i) { int w = g[v][i]; dfsLow(w); low[v] = min(low[v], low[w]); } } void dfsPost(int v) { static int time = 0; for(int i = 0; i < (int)g[v].size(); ++i) dfsPost(g[v][i]); post[v] = time++; } int add() // return pos { int k = pepsi.top(); pepsi.pop(); ball[k] = true; return k; } int remove(int pos) // return position of actual remove { if(!ball[pos]) cerr << "ERROR: remove from pepsi node" << endl; //cerr << "remove " << pos; for(int level = LOGN-1; level >= 0; --level) if(ball[par[level][pos]]) pos = par[level][pos]; ball[pos] = false; pepsi.push(pos); //cerr << " actual = " << pos << endl; return pos; } int main(int argc, char** argv) { scanf("%d %d", &n, &q); g.resize(n); for(int i = 0; i < LOGN; ++i) par[i].resize(n); ball.resize(n, false); low.resize(n); post.resize(n); layer.resize(n); readTree(n, par[0]); for(int i = 0; i < n; ++i) if(par[0][i] == i) root = i; else g[par[0][i]].push_back(i); par[0][root] = root; for(int level = 1; level < LOGN; ++level) for(int i = 0; i < n; ++i) par[level][i] = par[level-1][par[level-1][i]]; dfsLow(root); for(int i = 0; i < n; ++i) sort(g[i].begin(), g[i].end(), cmpLow); dfsPost(root); for(int i = 0; i < n; ++i) pepsi.push(i); for(int i = 0; i < q; ++i) { int t, k; scanf("%d %d", &t, &k); if(t == 1) // add k balls { for(int j = 0; j < k; ++j) { int pos = add(); if(j+1 == k) printf("%d\n", pos+1); } } else if(t == 2) // remove one ball from position k { --k; int actual = remove(k); printf("%d\n", layer[k]-layer[actual]); } else cerr << "ERROR: invalid t" << endl; } }
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 212 KB | Output is correct |
2 | Correct | 103 ms | 9124 KB | Output is correct |
3 | Correct | 64 ms | 9168 KB | Output is correct |
4 | Correct | 1 ms | 288 KB | Output is correct |
5 | Correct | 1 ms | 212 KB | Output is correct |
6 | Correct | 1 ms | 340 KB | Output is correct |
7 | Correct | 1 ms | 340 KB | Output is correct |
8 | Correct | 1 ms | 340 KB | Output is correct |
9 | Correct | 5 ms | 852 KB | Output is correct |
10 | Correct | 17 ms | 2392 KB | Output is correct |
11 | Correct | 86 ms | 9140 KB | Output is correct |
12 | Correct | 62 ms | 9168 KB | Output is correct |
13 | Correct | 87 ms | 9072 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 38 ms | 4812 KB | Output is correct |
2 | Correct | 128 ms | 17644 KB | Output is correct |
3 | Correct | 91 ms | 12888 KB | Output is correct |
4 | Correct | 64 ms | 5732 KB | Output is correct |
5 | Correct | 54 ms | 5936 KB | Output is correct |
6 | Correct | 51 ms | 5964 KB | Output is correct |
7 | Correct | 54 ms | 5100 KB | Output is correct |
8 | Correct | 38 ms | 4824 KB | Output is correct |
9 | Correct | 124 ms | 17296 KB | Output is correct |
10 | Correct | 141 ms | 17624 KB | Output is correct |
11 | Correct | 112 ms | 17572 KB | Output is correct |
12 | Correct | 121 ms | 15764 KB | Output is correct |
13 | Correct | 85 ms | 19572 KB | Output is correct |
14 | Correct | 72 ms | 12896 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 52 ms | 9256 KB | Output is correct |
2 | Correct | 154 ms | 15580 KB | Output is correct |
3 | Correct | 108 ms | 17696 KB | Output is correct |
4 | Correct | 84 ms | 13804 KB | Output is correct |
5 | Correct | 87 ms | 14056 KB | Output is correct |
6 | Correct | 94 ms | 14148 KB | Output is correct |
7 | Correct | 91 ms | 12276 KB | Output is correct |
8 | Correct | 105 ms | 17664 KB | Output is correct |
9 | Correct | 130 ms | 17476 KB | Output is correct |
10 | Correct | 161 ms | 17788 KB | Output is correct |
11 | Correct | 140 ms | 17756 KB | Output is correct |
12 | Correct | 176 ms | 15552 KB | Output is correct |
13 | Correct | 161 ms | 22328 KB | Output is correct |
14 | Correct | 102 ms | 13288 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 171 ms | 17516 KB | Output is correct |
2 | Correct | 140 ms | 16192 KB | Output is correct |
3 | Correct | 96 ms | 21956 KB | Output is correct |
4 | Correct | 172 ms | 17552 KB | Output is correct |
5 | Correct | 135 ms | 17744 KB | Output is correct |
6 | Correct | 110 ms | 17704 KB | Output is correct |
7 | Correct | 146 ms | 16132 KB | Output is correct |
8 | Correct | 109 ms | 21912 KB | Output is correct |
9 | Correct | 68 ms | 12932 KB | Output is correct |