# | 제출 시각 | 아이디 | 문제 | 언어 | 결과 | 실행 시간 | 메모리 |
---|---|---|---|---|---|---|---|
667236 | 2022-11-30T21:30:45 Z | AmirH | Ball Machine (BOI13_ballmachine) | C++14 | 637 ms | 49140 KB |
#include<iostream> #include<algorithm> #include<math.h> #include<vector> #include<bitset> #include<queue> #include<queue> #include<deque> #include<set> #include<map> #include<unordered_map> #include<list> #include<utility> #include<stack> using namespace std; typedef long long ll; typedef long double ld; typedef pair <ll, ll> pll; typedef pair <int, int> pii; #define cl clear #define F first #define S second #define pb push_back #define Sz(x) int((x).size()) #define all(x) (x).begin(), (x).end() #define faster ios::sync_with_stdio(0), cin.tie(0), cout.tie(0) const int MAX_N = 2e5 + 25; const ll INF = 1e18; const int inf = 1e9; void free() { #ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif } vector<int> vtx[MAX_N]; set<pii> adj[MAX_N]; int mini[MAX_N]; vector<int> res; int par[MAX_N]; set<int> notseen; int ar[MAX_N]; int pr[MAX_N]; int height[MAX_N]; int lcm[MAX_N][20]; int listpo[MAX_N]; int get_height(int v, int h) { if(h == 0) return v; int max_z = listpo[h]; return get_height(lcm[v][max_z], h - (1 << max_z)); } int get_last_seen(int v) { int l = 0, r = height[v] + 1; while(r - l > 1) { int mid = (l + r) / 2; if(notseen.find(ar[get_height(v, mid)]) == notseen.end()) l = mid; else r = mid; } return get_height(v, l); } void find_po() { int j = 0; for(int i = 1; i <= 1e5; i++) { if(i >= (1 << (j + 1))) { j++; listpo[i] = j; } else listpo[i] = j; } } void rmq(int v) { queue<int> q; q.push(v); while(!q.empty()) { int x = q.front(); q.pop(); for(auto i : vtx[x]) { if(height[i] > height[x]) q.push(i); } for(int i = 0; (1 << i) <= height[x]; i++) { if(i == 0) lcm[x][i] = par[x]; else lcm[x][i] = lcm[lcm[x][i - 1]][i - 1]; } } } void dfs2(int v) { for(auto i : adj[v]) dfs2(i.second); res.pb(v); } void dfs(int v, int s) { mini[v] = v; for(auto i : vtx[v]) { if(i != s) { height[i] = height[v] + 1; dfs(i, v); mini[v] = min(mini[v], mini[i]); adj[v].insert({mini[i], i}); } } } int main() { faster; //free(); find_po(); int n, q; cin >> n >> q; int st; for(int i = 1; i <= n; i++) { int x; cin >> x; par[i] = x; if(x == 0) { st = i; } else { vtx[x].pb(i); vtx[i].pb(x); } } height[st] = 0; dfs(st, 0); dfs2(st); rmq(st); for(int i = 0; i < res.size(); i++) { ar[res[i]] = i + 1; pr[i + 1] = res[i]; } for(int i = 1; i <= n; i++) notseen.insert(i); while(q--) { int t, x; cin >> t >> x; if(t == 1) { int ft; while(x--) { ft = pr[*notseen.begin()]; notseen.erase(notseen.begin()); } cout << ft << '\n'; } if(t == 2) { int sec = get_last_seen(x); notseen.insert(ar[sec]); cout << height[x] - height[sec] << '\n'; } } }
Compilation message
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 7 ms | 14804 KB | Output is correct |
2 | Correct | 137 ms | 29900 KB | Output is correct |
3 | Correct | 79 ms | 30040 KB | Output is correct |
4 | Correct | 8 ms | 14852 KB | Output is correct |
5 | Correct | 8 ms | 14804 KB | Output is correct |
6 | Correct | 8 ms | 15060 KB | Output is correct |
7 | Correct | 8 ms | 14980 KB | Output is correct |
8 | Correct | 9 ms | 14992 KB | Output is correct |
9 | Correct | 14 ms | 15700 KB | Output is correct |
10 | Correct | 32 ms | 18608 KB | Output is correct |
11 | Correct | 153 ms | 29836 KB | Output is correct |
12 | Correct | 96 ms | 30120 KB | Output is correct |
13 | Correct | 120 ms | 29896 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 57 ms | 21316 KB | Output is correct |
2 | Correct | 519 ms | 43204 KB | Output is correct |
3 | Correct | 111 ms | 37828 KB | Output is correct |
4 | Correct | 154 ms | 23456 KB | Output is correct |
5 | Correct | 202 ms | 23432 KB | Output is correct |
6 | Correct | 202 ms | 23484 KB | Output is correct |
7 | Correct | 172 ms | 21964 KB | Output is correct |
8 | Correct | 57 ms | 21232 KB | Output is correct |
9 | Correct | 369 ms | 43504 KB | Output is correct |
10 | Correct | 518 ms | 43200 KB | Output is correct |
11 | Correct | 384 ms | 43132 KB | Output is correct |
12 | Correct | 414 ms | 39800 KB | Output is correct |
13 | Correct | 171 ms | 44992 KB | Output is correct |
14 | Correct | 105 ms | 37796 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 118 ms | 29064 KB | Output is correct |
2 | Correct | 566 ms | 40600 KB | Output is correct |
3 | Correct | 352 ms | 42060 KB | Output is correct |
4 | Correct | 237 ms | 37668 KB | Output is correct |
5 | Correct | 323 ms | 37744 KB | Output is correct |
6 | Correct | 323 ms | 37612 KB | Output is correct |
7 | Correct | 291 ms | 35424 KB | Output is correct |
8 | Correct | 305 ms | 42076 KB | Output is correct |
9 | Correct | 336 ms | 43460 KB | Output is correct |
10 | Correct | 582 ms | 43308 KB | Output is correct |
11 | Correct | 562 ms | 43452 KB | Output is correct |
12 | Correct | 556 ms | 40708 KB | Output is correct |
13 | Correct | 571 ms | 49140 KB | Output is correct |
14 | Correct | 141 ms | 37952 KB | Output is correct |
# | 결과 | 실행 시간 | 메모리 | Grader output |
---|---|---|---|---|
1 | Correct | 381 ms | 43524 KB | Output is correct |
2 | Correct | 503 ms | 40652 KB | Output is correct |
3 | Correct | 188 ms | 48876 KB | Output is correct |
4 | Correct | 390 ms | 43444 KB | Output is correct |
5 | Correct | 637 ms | 43348 KB | Output is correct |
6 | Correct | 415 ms | 43292 KB | Output is correct |
7 | Correct | 550 ms | 40580 KB | Output is correct |
8 | Correct | 216 ms | 48844 KB | Output is correct |
9 | Correct | 111 ms | 37940 KB | Output is correct |