# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
106310 | 2019-04-17T20:54:45 Z | RedNextCentury | Ball Machine (BOI13_ballmachine) | C++14 | 288 ms | 19480 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)> empty(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 = empty.top(); empty.pop(); ball[k] = true; return k; } int remove(int pos) // return position of actual remove { if(!ball[pos]) cerr << "ERROR: remove from empty 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; empty.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) empty.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 | 2 ms | 384 KB | Output is correct |
2 | Correct | 168 ms | 8680 KB | Output is correct |
3 | Correct | 68 ms | 8952 KB | Output is correct |
4 | Correct | 2 ms | 384 KB | Output is correct |
5 | Correct | 2 ms | 384 KB | Output is correct |
6 | Correct | 3 ms | 512 KB | Output is correct |
7 | Correct | 3 ms | 512 KB | Output is correct |
8 | Correct | 3 ms | 512 KB | Output is correct |
9 | Correct | 7 ms | 896 KB | Output is correct |
10 | Correct | 20 ms | 2492 KB | Output is correct |
11 | Correct | 133 ms | 8652 KB | Output is correct |
12 | Correct | 80 ms | 8952 KB | Output is correct |
13 | Correct | 121 ms | 8852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 39 ms | 4088 KB | Output is correct |
2 | Correct | 177 ms | 15608 KB | Output is correct |
3 | Correct | 82 ms | 12788 KB | Output is correct |
4 | Correct | 59 ms | 5120 KB | Output is correct |
5 | Correct | 59 ms | 4992 KB | Output is correct |
6 | Correct | 59 ms | 5084 KB | Output is correct |
7 | Correct | 59 ms | 4344 KB | Output is correct |
8 | Correct | 38 ms | 4088 KB | Output is correct |
9 | Correct | 161 ms | 15984 KB | Output is correct |
10 | Correct | 179 ms | 15696 KB | Output is correct |
11 | Correct | 136 ms | 15580 KB | Output is correct |
12 | Correct | 169 ms | 14168 KB | Output is correct |
13 | Correct | 140 ms | 17136 KB | Output is correct |
14 | Correct | 84 ms | 12816 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 79 ms | 8312 KB | Output is correct |
2 | Correct | 192 ms | 14476 KB | Output is correct |
3 | Correct | 190 ms | 15724 KB | Output is correct |
4 | Correct | 153 ms | 13120 KB | Output is correct |
5 | Correct | 140 ms | 12716 KB | Output is correct |
6 | Correct | 145 ms | 12632 KB | Output is correct |
7 | Correct | 133 ms | 11768 KB | Output is correct |
8 | Correct | 156 ms | 15624 KB | Output is correct |
9 | Correct | 225 ms | 16084 KB | Output is correct |
10 | Correct | 211 ms | 15984 KB | Output is correct |
11 | Correct | 212 ms | 15856 KB | Output is correct |
12 | Correct | 217 ms | 14584 KB | Output is correct |
13 | Correct | 288 ms | 19480 KB | Output is correct |
14 | Correct | 159 ms | 12776 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 235 ms | 16212 KB | Output is correct |
2 | Correct | 242 ms | 14568 KB | Output is correct |
3 | Correct | 142 ms | 19320 KB | Output is correct |
4 | Correct | 231 ms | 16240 KB | Output is correct |
5 | Correct | 209 ms | 15872 KB | Output is correct |
6 | Correct | 185 ms | 15880 KB | Output is correct |
7 | Correct | 192 ms | 14580 KB | Output is correct |
8 | Correct | 126 ms | 19344 KB | Output is correct |
9 | Correct | 95 ms | 12788 KB | Output is correct |