Submission #1184387

#TimeUsernameProblemLanguageResultExecution timeMemory
1184387son2008Ball Machine (BOI13_ballmachine)C++20
100 / 100
162 ms34936 KiB
#include<bits/stdc++.h> using namespace std; #define task "task" #define ii pair<int,int> #define fi first #define se second //#define int long long #define ll long long #define ld double #define mp make_pair #define lg2 30 #define iii pair<int,ii> #define iiii pair<ii,ii> //#define base 29 #define eps 1e-8 int dx[]= {0LL,0LL,1,-1,1,1,-1,-1}; int dy[]= {1,-1,0LL,0LL,1,-1,1,-1}; const int maxn=4e5+1; const int mod=1e9+7; int goc,id[maxn],pos[maxn],timer,mn[maxn],P[maxn][lg2+1],n,q; vector<int>a[maxn]; bool cmp(int x,int y) { return mn[x]<mn[y]; } void dfs(int u) { mn[u]=u; for(int v:a[u]) { dfs(v); P[v][0]=u; mn[u]=min(mn[v],mn[u]); } sort(a[u].begin(),a[u].end(),cmp); } void gan(int u) { for(int v:a[u]) { gan(v); } id[u]=++timer; pos[timer]=u; } struct FEN { int n; vector<int>bit; FEN(){}; FEN(int _n):bit(n+1,0),n(_n+1) { }; int get(int r) { int ret = 0; for (; r >= 0; r = (r & (r + 1)) - 1) ret += bit[r]; return ret; } int get(int l, int r) { return get(r) - get(l - 1); } void update(int idx, int delta) { for (; idx < n; idx = idx | (idx + 1)) bit[idx] += delta; } void updateRange(int l,int r,int val) { update(l,val); update(r+1,-val); } }bit; void init() { cin>>n>>q; for(int i=1;i<=n;i++) { int p; cin>>p; if(!p)goc=i; else a[p].push_back(i); } dfs(goc); gan(goc); for(int j=1;j<=lg2;j++) { for(int i=1;i<=n;i++) { P[i][j]=P[P[i][j-1]][j-1]; } } bit=FEN(n+2); for(int i=1;i<=n;i++)bit.update(i,-1); while(q--) { int t; cin>>t; if(t==1) { int k; cin>>k; int ans=0; for(int i=1;i<=k;i++) { int l=0,r=n; while(l<=r) { int mid=(l+r)/2; if(bit.get(mid)<0) { r=mid-1; ans=mid; } else l=mid+1; } // cout<<ans<<" "; bit.update(ans,1); } // cout<<ans<<'\n'; cout<<pos[ans]<<'\n'; } else { int u; cin>>u; int ans=0; for(int j=lg2;j>=0;j--) { if(P[u][j]&&bit.get(id[P[u][j]])==bit.get(id[P[u][j]]-1)) { ans+=(1<<j); u=P[u][j]; } } bit.update(id[u],-1); cout<<ans<<'\n'; } } } void process() { } signed main() { ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0); if(fopen(task".inp","r")) { freopen(task".inp","r",stdin); freopen(task".out","w",stdout); } int t=1; // cin>>t; while(t--) { init(); process(); cout<<'\n'; } cerr <<endl<< "TIME : " << clock() * 0.001 << "s" << endl ; }

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:152:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  152 |         freopen(task".inp","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~
ballmachine.cpp:153:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
  153 |         freopen(task".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...