# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
1027065 | 2024-07-18T20:09:48 Z | hasan2006 | Ball Machine (BOI13_ballmachine) | C++17 | 316 ms | 43360 KB |
#include <bits/stdc++.h> using namespace std; #define TL ios::sync_with_stdio(0),cin.tie(0),cout.tie(0); #define rall(s) s.rbegin(),s.rend() #define all(s) s.begin(),s.end() #define pb push_back #define se second #define fi first #define ll long long #define ld long double #define YES cout<<"YES\n" #define Yes cout<<"Yes\n" #define yes cout<<"yes\n" #define NO cout<<"NO\n" #define No cout<<"No\n" #define no cout<<"no\n" const int N = 1e5 + 9 , mod = 1e9 + 7; ll dp[N] , c[N] , d[N] , p[N][22] , timer = 0; vector<int>v[N]; void dfs(int n){ d[n] = n; for(auto to : v[n]) dfs(to); d[p[n][0]] = min(d[p[n][0]] , d[n]); } set<pair<int,int>>st , ss; void dfs1(int n){ dp[n] = dp[p[n][0]] + 1; vector<pair<int,int>>vc; for(int i =1; i <= 20; i++) p[n][i] = p[p[n][i - 1]][i - 1]; for(auto to : v[n]) vc.pb({d[to] , to}); sort(all(vc)); for(auto to : vc) dfs1(to.se); c[n] = ++timer; st.insert({c[n] , n}); } void solve() { ll n , q , i , j ,l ,r , x , y , s = 0 , f , k , m , mn = 1e18, mx = 0 ; cin>>n>>m; for(i = 1; i <= n; i++){ cin>>p[i][0]; v[p[i][0]].pb(i); if(p[i][0] == 0) x = i; } dfs(x); dfs1(x); while(m--){ cin>>k>>x; if(k == 1){ while(x--){ y = st.begin()->se; st.erase(st.begin()); } cout<<y<<"\n"; }else{ f = x; for(i = 20; i >= 0; i--) if(p[x][i] && st.find({c[p[x][i]] , p[x][i]}) == st.end()) x = p[x][i]; cout<<dp[f] - dp[x]<<"\n"; st.insert({c[x] , x}); } } } int main(){ TL; /*#ifndef ONLINE_JUDGE freopen("input.txt", "r", stdin); freopen("output.txt", "w", stdout); #endif*/ int t = 1; // cin>>t; while(t--) { solve(); } } // Author : حسن
Compilation message
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 1 ms | 6748 KB | Output is correct |
2 | Correct | 115 ms | 21960 KB | Output is correct |
3 | Correct | 38 ms | 22220 KB | Output is correct |
4 | Correct | 1 ms | 6744 KB | Output is correct |
5 | Correct | 1 ms | 6748 KB | Output is correct |
6 | Correct | 1 ms | 6748 KB | Output is correct |
7 | Correct | 2 ms | 6748 KB | Output is correct |
8 | Correct | 2 ms | 6748 KB | Output is correct |
9 | Correct | 6 ms | 7004 KB | Output is correct |
10 | Correct | 18 ms | 9816 KB | Output is correct |
11 | Correct | 94 ms | 21920 KB | Output is correct |
12 | Correct | 52 ms | 22100 KB | Output is correct |
13 | Correct | 81 ms | 21852 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 29 ms | 12792 KB | Output is correct |
2 | Correct | 239 ms | 35480 KB | Output is correct |
3 | Correct | 71 ms | 28616 KB | Output is correct |
4 | Correct | 79 ms | 15188 KB | Output is correct |
5 | Correct | 124 ms | 15440 KB | Output is correct |
6 | Correct | 107 ms | 15188 KB | Output is correct |
7 | Correct | 104 ms | 14160 KB | Output is correct |
8 | Correct | 32 ms | 12888 KB | Output is correct |
9 | Correct | 188 ms | 35808 KB | Output is correct |
10 | Correct | 249 ms | 35412 KB | Output is correct |
11 | Correct | 194 ms | 35412 KB | Output is correct |
12 | Correct | 222 ms | 32080 KB | Output is correct |
13 | Correct | 83 ms | 40528 KB | Output is correct |
14 | Correct | 49 ms | 28616 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 71 ms | 22124 KB | Output is correct |
2 | Correct | 227 ms | 32556 KB | Output is correct |
3 | Correct | 139 ms | 36432 KB | Output is correct |
4 | Correct | 146 ms | 30712 KB | Output is correct |
5 | Correct | 169 ms | 30680 KB | Output is correct |
6 | Correct | 163 ms | 30540 KB | Output is correct |
7 | Correct | 164 ms | 27984 KB | Output is correct |
8 | Correct | 150 ms | 36500 KB | Output is correct |
9 | Correct | 189 ms | 35892 KB | Output is correct |
10 | Correct | 316 ms | 35708 KB | Output is correct |
11 | Correct | 285 ms | 35588 KB | Output is correct |
12 | Correct | 297 ms | 32596 KB | Output is correct |
13 | Correct | 248 ms | 43360 KB | Output is correct |
14 | Correct | 86 ms | 28812 KB | Output is correct |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 195 ms | 35920 KB | Output is correct |
2 | Correct | 222 ms | 32596 KB | Output is correct |
3 | Correct | 93 ms | 43048 KB | Output is correct |
4 | Correct | 190 ms | 35924 KB | Output is correct |
5 | Correct | 278 ms | 35744 KB | Output is correct |
6 | Correct | 213 ms | 35548 KB | Output is correct |
7 | Correct | 247 ms | 32596 KB | Output is correct |
8 | Correct | 102 ms | 43092 KB | Output is correct |
9 | Correct | 52 ms | 28616 KB | Output is correct |