| # | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
|---|---|---|---|---|---|---|---|
| 77369 | 2018-09-26T21:44:20 Z | xiaowuc1 | Ball Machine (BOI13_ballmachine) | C++14 | 936 ms | 23492 KB |
#include <bits/stdc++.h>
/*
unsigned seed1 = std::chrono::system_clock::now().time_since_epoch().count();
mt19937 g1.seed(seed1);
ios_base::sync_with_stdio(false);
cin.tie(NULL);
*/
using namespace std;
const double PI = 2 * acos(0);
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef long double ld;
typedef vector<vector<ll>> matrix;
typedef pair<int, bool> pib;
const int MAX_N = 100000+1;
const int MAX_D = 16;
int lca[MAX_D][MAX_N];
int minValSubtree[MAX_N];
int depth[MAX_N];
vector<int> children[MAX_N];
int n;
int root;
int vertexOrder[MAX_N];
int _order;
bool ordercmp(int a, int b) {
return vertexOrder[a] < vertexOrder[b];
}
bool subtreecmp(int a, int b) {
return minValSubtree[a] < minValSubtree[b];
}
set<int, bool(*)(int, int)> avail(ordercmp);
void solve() {
int t;
scanf("%d", &t);
int k;
if(t == 1) {
// insert k
scanf("%d", &k);
int last;
while(k--) {
last = *avail.begin();
avail.erase(last);
}
printf("%d\n", last);
}
else {
// remove from k
scanf("%d", &k);
int ret = 0;
for(int d = MAX_D-1; d >= 0; d--) {
while(depth[k] >= (1<<d) && !avail.count(lca[d][k])) {
k = lca[d][k];
ret += 1 << d;
}
}
avail.insert(k);
printf("%d\n", ret);
}
}
void dfs(int curr) {
minValSubtree[curr] = curr;
for(int out: children[curr]) {
dfs(out);
minValSubtree[curr] = min(minValSubtree[curr], minValSubtree[out]);
}
}
void genMin() {
dfs(root);
}
void genOrder() {
stack<pib> s;
s.push(pib(root, false));
while(!s.empty()) {
pib curr = s.top();
s.pop();
if(curr.second) {
vertexOrder[curr.first] = _order++;
}
else {
s.push(pib(curr.first, true));
for(int out: children[curr.first]) {
s.push(pib(out, false));
}
}
}
}
void genLCA() {
queue<int> q;
q.push(root);
while(!q.empty()) {
int curr = q.front();
q.pop();
sort(children[curr].begin(), children[curr].end(), subtreecmp);
reverse(children[curr].begin(), children[curr].end());
for(int out: children[curr]) {
depth[out] = depth[curr]+1;
q.push(out);
}
}
for(int d = 1; d < MAX_D; d++) {
for(int i = 1; i <= n; i++) {
lca[d][i] = lca[d-1][lca[d-1][i]];
}
}
}
int main() {
int q;
scanf("%d%d", &n, &q);
for(int i = 1; i <= n; i++) {
scanf("%d", &lca[0][i]);
if(lca[0][i]) {
children[lca[0][i]].push_back(i);
}
else {
root = i;
}
}
genMin();
genLCA();
genOrder();
for(int i = 1; i <= n; i++) {
avail.insert(i);
}
while(q--) solve();
}
Compilation message
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 4 ms | 2808 KB | Output is correct |
| 2 | Correct | 272 ms | 12136 KB | Output is correct |
| 3 | Correct | 127 ms | 12180 KB | Output is correct |
| 4 | Correct | 4 ms | 12180 KB | Output is correct |
| 5 | Correct | 4 ms | 12180 KB | Output is correct |
| 6 | Correct | 5 ms | 12180 KB | Output is correct |
| 7 | Correct | 5 ms | 12180 KB | Output is correct |
| 8 | Correct | 6 ms | 12180 KB | Output is correct |
| 9 | Correct | 16 ms | 12180 KB | Output is correct |
| 10 | Correct | 55 ms | 12180 KB | Output is correct |
| 11 | Correct | 288 ms | 12208 KB | Output is correct |
| 12 | Correct | 119 ms | 12392 KB | Output is correct |
| 13 | Correct | 214 ms | 12392 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 87 ms | 12392 KB | Output is correct |
| 2 | Correct | 829 ms | 19840 KB | Output is correct |
| 3 | Correct | 143 ms | 19840 KB | Output is correct |
| 4 | Correct | 230 ms | 19840 KB | Output is correct |
| 5 | Correct | 341 ms | 19840 KB | Output is correct |
| 6 | Correct | 312 ms | 19840 KB | Output is correct |
| 7 | Correct | 301 ms | 19840 KB | Output is correct |
| 8 | Correct | 114 ms | 19840 KB | Output is correct |
| 9 | Correct | 611 ms | 20128 KB | Output is correct |
| 10 | Correct | 823 ms | 20128 KB | Output is correct |
| 11 | Correct | 588 ms | 20128 KB | Output is correct |
| 12 | Correct | 688 ms | 20128 KB | Output is correct |
| 13 | Correct | 221 ms | 21092 KB | Output is correct |
| 14 | Correct | 151 ms | 21092 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 219 ms | 21092 KB | Output is correct |
| 2 | Correct | 893 ms | 21092 KB | Output is correct |
| 3 | Correct | 449 ms | 21092 KB | Output is correct |
| 4 | Correct | 380 ms | 21092 KB | Output is correct |
| 5 | Correct | 514 ms | 21092 KB | Output is correct |
| 6 | Correct | 519 ms | 21092 KB | Output is correct |
| 7 | Correct | 471 ms | 21092 KB | Output is correct |
| 8 | Correct | 456 ms | 21092 KB | Output is correct |
| 9 | Correct | 560 ms | 21092 KB | Output is correct |
| 10 | Correct | 769 ms | 21092 KB | Output is correct |
| 11 | Correct | 816 ms | 21092 KB | Output is correct |
| 12 | Correct | 793 ms | 21092 KB | Output is correct |
| 13 | Correct | 743 ms | 23492 KB | Output is correct |
| 14 | Correct | 241 ms | 23492 KB | Output is correct |
| # | 결과 | 실행 시간 | 메모리 | Grader output |
|---|---|---|---|---|
| 1 | Correct | 718 ms | 23492 KB | Output is correct |
| 2 | Correct | 881 ms | 23492 KB | Output is correct |
| 3 | Correct | 299 ms | 23492 KB | Output is correct |
| 4 | Correct | 750 ms | 23492 KB | Output is correct |
| 5 | Correct | 936 ms | 23492 KB | Output is correct |
| 6 | Correct | 682 ms | 23492 KB | Output is correct |
| 7 | Correct | 833 ms | 23492 KB | Output is correct |
| 8 | Correct | 261 ms | 23492 KB | Output is correct |
| 9 | Correct | 142 ms | 23492 KB | Output is correct |