# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
110490 | 2019-05-11T00:14:13 Z | wilwxk | Ball Machine (BOI13_ballmachine) | C++11 | 1000 ms | 21368 KB |
#include <bits/stdc++.h> using namespace std; const int MAXN=1e5+5; const int LOGN=22; vector<int> g[MAXN]; int dp[MAXN][LOGN]; int prof[MAXN], gin[MAXN]; int marc[MAXN]; set<int> s; int n, q, root; int contv; void dfs(int cur, int p) { for(auto viz : g[cur]) { if(viz==p) continue; dp[viz][0]=cur; gin[cur]++; prof[viz]=prof[cur]+1; dfs(viz, cur); } } int pula(int cur) { for(int i=LOGN-1; i>=0; i--) { if(marc[dp[cur][i]]) cur=dp[cur][i]; } return cur; } int main() { scanf("%d %d", &n, &q); for(int i=1; i<=n; i++) { int a; scanf("%d", &a); if(a==0) root=i; else g[a].push_back(i), g[i].push_back(a); } dfs(root, root); for(int i=1; i<=n; i++) if(!gin[i]) s.insert(i); for(int i=1; i<LOGN; i++) { for(int j=1; j<=n; j++) dp[j][i]=dp[dp[j][i-1]][i-1]; } while(q--) { int a, x; scanf("%d %d", &a, &x); if(a==1) { int cur, p; while(x--) { cur= *s.begin(); p=dp[cur][0]; s.erase(s.begin()); marc[cur]=1; gin[p]--; if(!gin[p]) s.insert(p); } printf("%d\n", cur); } else { int cur=pula(x); int p=dp[cur][0]; marc[cur]=0; gin[p]++; s.erase(p); printf("%d\n", prof[x]-prof[cur]); } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1067 ms | 2688 KB | Time limit exceeded |
2 | Execution timed out | 1067 ms | 13304 KB | Time limit exceeded |
3 | Incorrect | 102 ms | 13560 KB | Output isn't correct |
4 | Execution timed out | 1068 ms | 2688 KB | Time limit exceeded |
5 | Execution timed out | 1073 ms | 2816 KB | Time limit exceeded |
6 | Incorrect | 5 ms | 2816 KB | Output isn't correct |
7 | Execution timed out | 1063 ms | 2816 KB | Time limit exceeded |
8 | Execution timed out | 1075 ms | 2816 KB | Time limit exceeded |
9 | Execution timed out | 1073 ms | 3328 KB | Time limit exceeded |
10 | Execution timed out | 1066 ms | 5468 KB | Time limit exceeded |
11 | Execution timed out | 1074 ms | 13304 KB | Time limit exceeded |
12 | Incorrect | 121 ms | 13600 KB | Output isn't correct |
13 | Execution timed out | 1073 ms | 13244 KB | Time limit exceeded |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1052 ms | 6144 KB | Time limit exceeded |
2 | Execution timed out | 1075 ms | 20344 KB | Time limit exceeded |
3 | Incorrect | 132 ms | 19444 KB | Output isn't correct |
4 | Execution timed out | 1065 ms | 8136 KB | Time limit exceeded |
5 | Execution timed out | 1067 ms | 8192 KB | Time limit exceeded |
6 | Execution timed out | 1068 ms | 8312 KB | Time limit exceeded |
7 | Execution timed out | 1072 ms | 7672 KB | Time limit exceeded |
8 | Execution timed out | 1051 ms | 6144 KB | Time limit exceeded |
9 | Execution timed out | 1071 ms | 19704 KB | Time limit exceeded |
10 | Execution timed out | 1054 ms | 20216 KB | Time limit exceeded |
11 | Execution timed out | 1072 ms | 20348 KB | Time limit exceeded |
12 | Execution timed out | 1072 ms | 18808 KB | Time limit exceeded |
13 | Execution timed out | 1088 ms | 18300 KB | Time limit exceeded |
14 | Incorrect | 131 ms | 19444 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 94 ms | 11640 KB | Output isn't correct |
2 | Incorrect | 230 ms | 19436 KB | Output isn't correct |
3 | Correct | 193 ms | 17528 KB | Output is correct |
4 | Incorrect | 150 ms | 16504 KB | Output isn't correct |
5 | Incorrect | 172 ms | 16936 KB | Output isn't correct |
6 | Incorrect | 169 ms | 17016 KB | Output isn't correct |
7 | Incorrect | 140 ms | 16040 KB | Output isn't correct |
8 | Correct | 144 ms | 17656 KB | Output is correct |
9 | Incorrect | 285 ms | 20208 KB | Output isn't correct |
10 | Incorrect | 263 ms | 20596 KB | Output isn't correct |
11 | Incorrect | 231 ms | 20572 KB | Output isn't correct |
12 | Incorrect | 234 ms | 19392 KB | Output isn't correct |
13 | Correct | 228 ms | 21368 KB | Output is correct |
14 | Incorrect | 216 ms | 19504 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Execution timed out | 1062 ms | 19580 KB | Time limit exceeded |
2 | Execution timed out | 1075 ms | 19296 KB | Time limit exceeded |
3 | Execution timed out | 1081 ms | 20472 KB | Time limit exceeded |
4 | Execution timed out | 1067 ms | 19832 KB | Time limit exceeded |
5 | Execution timed out | 1063 ms | 20388 KB | Time limit exceeded |
6 | Execution timed out | 1066 ms | 20344 KB | Time limit exceeded |
7 | Execution timed out | 1079 ms | 19200 KB | Time limit exceeded |
8 | Execution timed out | 1074 ms | 20344 KB | Time limit exceeded |
9 | Incorrect | 155 ms | 19528 KB | Output isn't correct |