# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
160487 | 2019-10-27T18:32:01 Z | tushar_2658 | Ball Machine (BOI13_ballmachine) | C++14 | 1000 ms | 33912 KB |
#include "bits/stdc++.h" using namespace std; const int maxn = 100005; int par[maxn], root; vector<int> edges[maxn]; int depth[maxn], dp[maxn], n, m; void dfs(int x, int p){ depth[x] = depth[p] + 1; dp[x] = x; vector<pair<int, int>> all; for(auto i : edges[x]){ if(i == p)continue; dfs(i, x); all.push_back({dp[i], i}); dp[x] = min(dp[x], dp[i]); } sort(all.begin(), all.end()); edges[x].clear(); for(auto i : all){ edges[x].push_back(i.second); } edges[x].push_back(p); } set<pair<int, int>> st; int ed[maxn], cnt = 0; void dfs1(int x, int p){ for(auto i : edges[x]){ if(i == p)continue; dfs1(i, x); } ed[x] = ++cnt; st.insert({cnt, x}); } int sparse[maxn][22]; void build(){ for(int i = 1; i <= n; i++){ sparse[i][0] = par[i]; } for(int j = 1; j < 20; j++){ for(int i = 1; i <= n; i++){ if(sparse[i][j - 1] != 0){ sparse[i][j] = sparse[sparse[i][j - 1]][j - 1]; } } } } bool status[maxn]; int first_empty(int x){ for(int i = 20; i >= 0; i--){ if(sparse[x][i] != 0 && status[sparse[x][i]] != 0){ x = sparse[x][i]; } } return x; } int main(int argc, char const *argv[]) { // freopen("in.txt", "r", stdin); scanf("%d %d", &n, &m); for(int i = 1; i <= n; i++){ int x; scanf("%d", &x); if(x != 0){ edges[i].push_back(x); edges[x].push_back(i); par[i] = x; }else { root = i; } } dfs(root, -1); dfs1(root, -1); build(); while(m--){ int t, x; scanf("%d %d", &t, &x); if(t == 1){ pair<int, int> last; for(int i = 0; i < x; i++){ last = *st.begin(); st.erase(st.begin()); status[last.second] = 1; } printf("%d\n", last.second); }else { int ff = first_empty(x); status[ff] = 0; st.insert({ed[x], x}); printf("%d\n", depth[x] - depth[ff]); } } return 0; }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2808 KB | Output isn't correct |
2 | Execution timed out | 1079 ms | 14840 KB | Time limit exceeded |
3 | Correct | 113 ms | 15072 KB | Output is correct |
4 | Execution timed out | 1083 ms | 2684 KB | Time limit exceeded |
5 | Incorrect | 5 ms | 2680 KB | Output isn't correct |
6 | Correct | 5 ms | 2808 KB | Output is correct |
7 | Execution timed out | 1071 ms | 2812 KB | Time limit exceeded |
8 | Incorrect | 5 ms | 2808 KB | Output isn't correct |
9 | Execution timed out | 1090 ms | 3448 KB | Time limit exceeded |
10 | Execution timed out | 1088 ms | 5752 KB | Time limit exceeded |
11 | Incorrect | 154 ms | 14840 KB | Output isn't correct |
12 | Correct | 141 ms | 15060 KB | Output is correct |
13 | Incorrect | 149 ms | 15060 KB | Output isn't correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 54 ms | 8696 KB | Output is correct |
2 | Correct | 267 ms | 27292 KB | Output is correct |
3 | Correct | 145 ms | 21220 KB | Output is correct |
4 | Correct | 105 ms | 10420 KB | Output is correct |
5 | Correct | 102 ms | 10208 KB | Output is correct |
6 | Correct | 91 ms | 10232 KB | Output is correct |
7 | Correct | 93 ms | 8864 KB | Output is correct |
8 | Correct | 65 ms | 8632 KB | Output is correct |
9 | Correct | 223 ms | 27384 KB | Output is correct |
10 | Correct | 246 ms | 27512 KB | Output is correct |
11 | Correct | 223 ms | 27340 KB | Output is correct |
12 | Correct | 339 ms | 23796 KB | Output is correct |
13 | Correct | 170 ms | 30180 KB | Output is correct |
14 | Correct | 136 ms | 21176 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 113 ms | 15192 KB | Output is correct |
2 | Correct | 274 ms | 24400 KB | Output is correct |
3 | Correct | 187 ms | 27760 KB | Output is correct |
4 | Correct | 171 ms | 22520 KB | Output is correct |
5 | Correct | 264 ms | 22560 KB | Output is correct |
6 | Correct | 180 ms | 22552 KB | Output is correct |
7 | Correct | 178 ms | 20036 KB | Output is correct |
8 | Correct | 204 ms | 27700 KB | Output is correct |
9 | Correct | 271 ms | 27512 KB | Output is correct |
10 | Correct | 281 ms | 27612 KB | Output is correct |
11 | Correct | 285 ms | 27632 KB | Output is correct |
12 | Correct | 278 ms | 24440 KB | Output is correct |
13 | Correct | 283 ms | 33912 KB | Output is correct |
14 | Correct | 219 ms | 21392 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Incorrect | 257 ms | 27608 KB | Output isn't correct |
2 | Incorrect | 262 ms | 24440 KB | Output isn't correct |
3 | Correct | 197 ms | 33772 KB | Output is correct |
4 | Incorrect | 251 ms | 27640 KB | Output isn't correct |
5 | Incorrect | 268 ms | 27512 KB | Output isn't correct |
6 | Incorrect | 219 ms | 27476 KB | Output isn't correct |
7 | Incorrect | 268 ms | 24400 KB | Output isn't correct |
8 | Correct | 183 ms | 33656 KB | Output is correct |
9 | Correct | 133 ms | 21220 KB | Output is correct |