제출 #492756

#제출 시각아이디문제언어결과실행 시간메모리
492756nickmet2004Ball Machine (BOI13_ballmachine)C++11
100 / 100
302 ms27956 KiB
#include<bits/stdc++.h> using namespace std; const int N = 1e5 + 5; int n , q; vector<int> adj[N]; int S[N] , P[N][20] , R , A[N] , B[N] ,C[N], b; void dfs(int u, int p){ S[u]=u; P[u][0]= p; for(int i = 1; i<= 18; ++i) P[u][i]= P[P[u][i - 1]][i - 1]; for(int v : adj[u]){ dfs(v,u); S[u] = min(S[u], S[v]); } } void DFS(int u){ for(int v : adj[u]) DFS(v); B[++b] = u; } bool cmp(int a, int b){ return S[a] < S[b]; } int k = 0; int Q(int u){ for(int i = 17; ~i; --i){ int y = P[u][i]; if(C[y]) u = y ,k += (1 <<i); } return u; } int main (){ ios_base::sync_with_stdio(0); cin.tie(0); cin >> n >> q; int a; for(int i= 1; i <=n; ++i){ cin >> a; if(a==0)R = i; else adj[a].emplace_back(i); } for(int i = 1;i <= n; ++i) S[i] = 2e9; dfs(R,0); for(int i= 1; i<= n; ++i)sort(adj[i].begin() ,adj[i].end() , cmp); DFS(R); //for(int i = 1; i<= n; ++i)cout << B[i] << " ";cout << endl; for(int i = 1; i <= n; ++i) A[B[i]] = i; set<int> s; for(int i = 1; i<= n; ++i)s.insert(i); while(q--){ int d; cin >> d; if(d==1){ int x; cin >> x; int g = 0; while(x--){ g = *s.begin(); s.erase(s.begin()); C[B[g]] =1; } cout << B[g]<<endl; }else{ int u; cin>>u; int h = Q(u); cout << k << endl;k=0; s.insert(A[h]); C[h]=0; } } return 0; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...