Submission #786728

#TimeUsernameProblemLanguageResultExecution timeMemory
786728vjudge1Ball Machine (BOI13_ballmachine)C++17
8.57 / 100
1091 ms38652 KiB
//i_love_aisukiuwu #include <bits/stdc++.h> using namespace std; #ifdef LOCAL #include "/home/trucmai/.vim/tools.h" #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl; #else #define debug(x...) #endif void open(){ if(fopen("i.inp","r")){ freopen("i.inp","r",stdin); freopen("o.out","w",stdout); } } #define ll long long #define all(a) (a).begin(), (a).end() #define vi vector<ll> #define pi pair<ll,ll> #define pii pair<ll,pair<ll,ll>> #define fi first #define se second #define gcd __gcd #define mset(a,v) memset(a, v, sizeof(a)) #define endl '\n' #define spc " " const int MN1 = 1e5 + 5,MN2 = 1e4 + 5,LOG = 27; const ll MOD = 1e9 + 7,INF = 1e9; ll n,q,p[MN1],root; ll mx[MN1],h[MN1],sz[MN1]; ll up[MN1][LOG]; bool col[MN1]; vector<ll>adj[MN1]; ll timer = 0; void dfs(ll u,ll pre){ mx[u] = u; sz[u] = 1; for(ll v : adj[u]){ if(v == pre) continue; h[v] = h[u] + 1; up[v][0] = u; for(ll i = 1;i < LOG;++i) up[v][i] = up[up[v][i-1]][i-1]; dfs(v,u); mx[u] = min(mx[u],mx[v]); sz[u] += sz[v]; } } ll dfs_upd(ll u,ll cnt){ for(ll &v : adj[u]){ if(!col[v]){ ll tmp = min(cnt,sz[v]), x = dfs_upd(v,tmp); if(cnt == tmp) return x; } } if(cnt > 0) --cnt,col[u] = true; return u; } void solve(){ cin>>n>>q; for(ll i = 1;i <= n;++i){ cin>>p[i]; if(p[i] == 0){root = i; continue;} adj[p[i]].push_back(i); } dfs(root,0); while(q--){ ll t,u; cin>>t>>u; if(t == 1) cout<<dfs_upd(root,u)<<endl; else{ ll v = u; for(ll i = LOG;i >= 0;--i) if(col[up[v][i]]) v = up[v][i]; col[v] = false; cout<<h[u] - h[v]<<endl; } } } signed main(){ cin.tie(0) -> sync_with_stdio(0); open(); ll t = 1; //cin>>t; while(t--) solve(); cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n"; }

Compilation message (stderr)

ballmachine.cpp: In function 'void open()':
ballmachine.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...