Submission #834137

#TimeUsernameProblemLanguageResultExecution timeMemory
834137christinelynnBall Machine (BOI13_ballmachine)C++17
25 / 100
207 ms131072 KiB
#include <bits/stdc++.h> #define inf INT_MAX #define longlonginf LONG_LONG_MAX #define mod 998244353 #define MAXN 100005 #define pii pair<ll,ll> #define ll long long #define deb(x) cerr<<"[ "<<#x<<" = "<<x<<" ]"; #define yes() cout<<"YES\n"; #define no() cout<<"NO\n"; using namespace std; ll n,m,kk,q,x; ll h; ll ans = 0; string subtask; ll t; ll s,f; ll par[MAXN]; vector<vector<ll>> child(MAXN); ll root; ll v[4*MAXN]; ll k; bool vis[4*MAXN]; void build(ll x){ if(child[x].size() == 0 ){ v[x] = x; return; } build(child[x][0]); build(child[x][1]); v[x] = min(x,min(v[child[x][0]],v[child[x][1]])); } void add(ll x){ //cout<<"traversing ; "<<x<<"\n"; if( child[x].size() == 0 ) { //cout<<"visiting : "<<x<<"\n"; vis[x] = 1; ans = x; return; } if( vis[child[x][0]] && vis[child[x][1]] ){ //cout<<"visiting : "<<x<<"\n"; vis[x] = 1; ans = x; return; } if( v[child[x][0]] < v[child[x][1]] ){ if( vis[child[x][0]] == 1 ) add(child[x][1]); else add(child[x][0]); } else{ if( vis[child[x][1]] == 0 ) add(child[x][1]); else add(child[x][0]); } } void remove(int x,ll d){ if( vis[par[x]] == 0 ){ vis[x] = 0; //cout<<"erased : "<<x<<"\n"; cout<<d<<"\n"; return; } remove(par[x],d+1); } void solve(){ cin>>n>>q; for(int i = 1 ; i <= n ; i++){ cin>>x; if( x == 0 ) root = i; par[i] = x; child[x].push_back(i); } build(root); memset(vis,0,sizeof(vis)); while(q--){ cin>>x; if( x == 1 ){ cin>>k; while(k--){ //cout<<"! "<<ans<<"\n"; add(root); } cout<<ans<<"\n"; } else{ cin>>k; remove(k,0); } } } int main(){ ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); int T = 1; //cin>>T; for(int i = 0 ; i < T ; i++){ //cout<<"Case #"<<i+1<<": "; solve(); } return 0; } /* you thought u declared it huh? not i but x logical operator wrong example/proof thoroughly wrong variables thinking it wrong bruh just try some test case capitals ;-; wrong data structure lol count memory usement corner case oversized array orders statements size initializer while con map -> array wrong digits?? swapped variables?? check if theres any variabled that got declared twice find some pattern name collision constraints??! mod !! resets */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...