# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
196860 | 2020-01-17T10:15:18 Z | dantoh000 | Ball Machine (BOI13_ballmachine) | C++14 | 365 ms | 23672 KB |
#include <bits/stdc++.h> using namespace std; const int N = 100005; int n,q; vector<int> adjlist[N]; int ct = 1; int p[N][20]; int d[N], mn[N], l[N], r[N], pos[N]; int fw[N], id[N]; int root; void up(int x, int v){ while (x <= N){ fw[x] += v; x += x&(-x); } } int sum(int x){ int res = 0; while (x){ res += fw[x]; x -= x&(-x); } return res; } int sum(int s, int e){ return sum(e)-sum(s-1); } void print(){ for (int i = 1; i <= n; i++) printf("%d ",sum(i,i)); printf("\n");} void dfs(int u){ mn[u] = u; for (auto v : adjlist[u]){ d[v] = d[u]+1; for (int k = 1; k < 20; k++){ p[v][k] = p[p[v][k-1]][k-1]; if (p[v][k] == 0) break; } dfs(v); mn[u] = min(mn[u],mn[v]); } return; } void visit(int u){ l[u] = ct; for (auto v : adjlist[u]){ if (mn[v] == mn[u]) visit(v); } for (auto v : adjlist[u]){ if (mn[v] != mn[u]) visit(v); } id[ct] = u; pos[u] = ct; r[u] = ct++; } int add(){ int lo = 1, hi = n; while (lo + 1 < hi){ int mid = (lo+hi)/2; if (sum(mid) != mid) hi = mid; else lo = mid; } if (lo + 1 == hi){ if (sum(lo) != lo) hi = lo; else lo = hi; } up(lo,1); ///print(); return id[lo]; } int rem(int x){ int ans = 0; for (int k = 19; k >= 0; k--){ int P = p[x][k]; if (P && sum(l[P],r[P]) == r[P]-l[P]+1){ x = P; ans ^= (1<<k); } } up(pos[x],-1); ///print(); return ans; } int main(){ scanf("%d%d",&n,&q); for (int i = 1; i <= n; i++){ scanf("%d",&p[i][0]); if (p[i][0] == 0) root = i; else adjlist[p[i][0]].push_back(i); } p[root][0] = root; dfs(root); visit(root); for (int i = 0; i < q; i++){ int t,x; scanf("%d%d",&t,&x); if (t == 1){ int last; while (x--){ last = add(); //printf("added %d %d\n",i,last); } printf("%d\n",last); } else { printf("%d\n",rem(x)); } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 4 ms | 2812 KB | Output is correct |
2 | Correct | 162 ms | 11216 KB | Output is correct |
3 | Correct | 88 ms | 11256 KB | Output is correct |
4 | Incorrect | 5 ms | 2808 KB | Output isn't correct |
5 | Correct | 5 ms | 2808 KB | Output is correct |
6 | Correct | 5 ms | 2936 KB | Output is correct |
7 | Incorrect | 5 ms | 2936 KB | Output isn't correct |
8 | Correct | 5 ms | 2808 KB | Output is correct |
9 | Correct | 11 ms | 3320 KB | Output is correct |
10 | Correct | 33 ms | 4984 KB | Output is correct |
11 | Correct | 172 ms | 11228 KB | Output is correct |
12 | Correct | 76 ms | 11260 KB | Output is correct |
13 | Incorrect | 119 ms | 11004 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 52 ms | 7032 KB | Output is correct |
2 | Correct | 365 ms | 18936 KB | Output is correct |
3 | Correct | 103 ms | 14732 KB | Output is correct |
4 | Incorrect | 118 ms | 8056 KB | Output isn't correct |
5 | Incorrect | 139 ms | 8044 KB | Output isn't correct |
6 | Correct | 123 ms | 7800 KB | Output is correct |
7 | Incorrect | 120 ms | 7076 KB | Output isn't correct |
8 | Correct | 57 ms | 7004 KB | Output is correct |
9 | Incorrect | 279 ms | 19168 KB | Output isn't correct |
10 | Correct | 313 ms | 18984 KB | Output is correct |
11 | Correct | 220 ms | 18552 KB | Output is correct |
12 | Correct | 294 ms | 16912 KB | Output is correct |
13 | Correct | 196 ms | 20856 KB | Output is correct |
14 | Correct | 106 ms | 14836 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 125 ms | 11344 KB | Output isn't correct |
2 | Incorrect | 335 ms | 17444 KB | Output isn't correct |
3 | Correct | 245 ms | 19320 KB | Output is correct |
4 | Incorrect | 203 ms | 16120 KB | Output isn't correct |
5 | Correct | 225 ms | 15788 KB | Output is correct |
6 | Correct | 216 ms | 15736 KB | Output is correct |
7 | Incorrect | 204 ms | 14544 KB | Output isn't correct |
8 | Correct | 181 ms | 19480 KB | Output is correct |
9 | Incorrect | 249 ms | 19492 KB | Output isn't correct |
10 | Correct | 269 ms | 19164 KB | Output is correct |
11 | Correct | 257 ms | 19024 KB | Output is correct |
12 | Incorrect | 330 ms | 17528 KB | Output isn't correct |
13 | Correct | 337 ms | 23672 KB | Output is correct |
14 | Incorrect | 136 ms | 15156 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 257 ms | 19524 KB | Output isn't correct |
2 | Incorrect | 249 ms | 17528 KB | Output isn't correct |
3 | Correct | 159 ms | 23160 KB | Output is correct |
4 | Incorrect | 258 ms | 19448 KB | Output isn't correct |
5 | Correct | 271 ms | 19056 KB | Output is correct |
6 | Incorrect | 273 ms | 18688 KB | Output isn't correct |
7 | Incorrect | 246 ms | 17400 KB | Output isn't correct |
8 | Correct | 161 ms | 23160 KB | Output is correct |
9 | Correct | 106 ms | 14888 KB | Output is correct |