제출 #36538

#제출 시각아이디문제언어결과실행 시간메모리
36538Dat160601Ball Machine (BOI13_ballmachine)C++14
41.92 / 100
269 ms34476 KiB
#include <bits/stdc++.h> using namespace std; #define pb push_back #define mp make_pair #define fi first #define se second int n,q; int par[100007],mi[100007],root,num[100007],cnt=0; int op,x; int p[20][100007]; bool stat[100007]; vector <int> edge[100007],edge2[100007]; priority_queue < pair<int,int> , vector < pair<int,int> > , greater < pair<int,int> > > pr; void read(int &k){ int x; scanf("%d",&x); k=x; } void print(int x){ printf("%d\n",x); } void dfs(int u){ vector < pair<int,int> > cur; mi[u]=u; for(int i=0;i<(int)edge[u].size();i++){ int v=edge[u][i]; if(v==par[u]) continue; dfs(v); mi[u]=min(mi[u],mi[v]); cur.pb(mp(mi[v],v)); } sort(cur.begin(),cur.end()); for(int i=0;i<(int)cur.size();i++){ edge2[u].pb(cur[i].se); } } void dfs2(int u){ for(int i=0;i<(int)edge2[u].size();i++){ int v=edge2[u][i]; if(v==par[u]) continue; dfs2(v); } cnt++; num[u]=cnt; } int main(){ read(n); read(q); for(int i=1;i<=n;i++){ read(par[i]); edge[par[i]].pb(i); p[0][i]=par[i]; if(par[i]==0) root=i; mi[i]=1e9; } dfs(root); dfs2(root); for(int i=1;i<=n;i++) pr.push(mp(num[i],i)); for(int i=1;i<=19;i++){ for(int j=1;j<=n;j++){ p[i][j]=p[i-1][p[i-1][j]]; } } while(q--){ read(op); read(x); if(op==1){ int ans=0; while(x>0){ x--; int u=pr.top().se; stat[u]=true; ans=u; pr.pop(); } print(ans); } else{ int ans=0; for(int i=19;i>=0;i--){ int pr=p[i][x]; if(stat[pr]){ x=pr; ans+=(1<<i); } } stat[x]=false; print(ans); } } }

컴파일 시 표준 에러 (stderr) 메시지

ballmachine.cpp: In function 'void read(int&)':
ballmachine.cpp:16:16: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d",&x);
                ^
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...