이 제출은 이전 버전의 oj.uz에서 채점하였습니다. 현재는 제출 당시와는 다른 서버에서 채점을 하기 때문에, 다시 제출하면 결과가 달라질 수도 있습니다.
#include<bits/stdc++.h>
using namespace std;
const int N = 1e5 + 5;
int n , q , A[N],B[N];
vector<int> adj[N] , v;
int P[N][20] , d[N] ,X[N];
int k,R;
void dfs(int u , int p){
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]){
d[v] = d[u] + 1;
dfs(v,u);
}
v.emplace_back(u);
}
int ans = 0;
int F(int u){
for(int i = 18; ~i; --i){
int y= P[u][i];
if(X[y]) u = y , ans += (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;
if(a)adj[a].emplace_back(i);
}
for(int i = 1; i <= n; ++i)sort(adj[i].begin() , adj[i].end());
dfs(R,0);
//for(int x : v)cout << x << " ";cout << endl;
for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
int t;
set<int> free;
for(int i= 1; i<= n; ++i)free.insert(i);
while(q--){
cin >> t;
if(t==1){
int k;
cin >>k;
int x;
for(int i = 0; i < k; ++i){
if(free.begin()==free.end())break;
x = *free.begin();
X[B[x]] = 1;
free.erase(free.begin());
}
//cout << k << "k "<<endl;
cout << B[x] <<endl;
}else{
int h; cin >> h;
int v = F(h);
//cout << v << " v" << endl;
// cout << v << "v"<<endl;
free.insert(A[v]);
X[v]=0;
cout << ans << endl; ans = 0;
}
}
}
컴파일 시 표준 에러 (stderr) 메시지
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:38:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
38 | for(int i = 0; i < v.size(); ++i) A[v[i]] = i+1 , B[i + 1] = v[i];
| ~~^~~~~~~~~~
ballmachine.cpp:55:24: warning: 'x' may be used uninitialized in this function [-Wmaybe-uninitialized]
55 | cout << B[x] <<endl;
| ^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |