This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define db double
#define pairll pair<ll,ll>
#define lpairll pair<ll,pairll>
#define repp(i,a,b) for (ll i = a; i <= b; i++)
#define repz(i,a,b) for (ll i = a; i < b; i++)
#define repm(i,a,b) for (ll i = a; i >= b; i--)
#define fr first
#define sc second
#define mp make_pair
#define pb push_back
const ll N = 1e5+5, MOD = 1e9+7;
ll tc = 1, n, m, ar[N], br[N], used[N], cap[N], rev[N];
ll x, y, k, root, cur;
string s, s1, s2, ye = "YES", no = "NO";
vector<ll> ed[N];
ll ins = 0, roldown;
void input(){
cin >> n >> m;
repp(i,1,n){
cin >> ar[i];
if (ar[i] == 0){
root = i;
}
else{
ed[ar[i]].pb(i);
rev[i] = ar[i];
}
}
}
void buildcap(ll idx){
cap[idx] = 1;
for (auto i : ed[idx]){
buildcap(i);
cap[idx] += cap[i];
}
}
void insball(ll idx){
bool fnd = 0;
for (auto i : ed[idx]){
if (used[i] == cap[i]) continue;
fnd = 1;
insball(i);
break;
}
if (!fnd){
cur = idx;
}
used[idx]++;
}
void sub1(){
buildcap(root);
while(m--){
cin >> x >> y;
if (x == 1){
repp(i,1,y){
insball(root);
}
cout << cur << endl;
}
else{
roldown = 0;
while(1){
if (y == root) break;
if (cap[rev[y]] != used[rev[y]]){
break;
}
y = rev[y];
roldown++;
}
cout << roldown << endl;
used[y]--;
}
}
}
void solve(){
bool ok1 = 1;
repp(i,1,n){
sort(ed[i].begin(),ed[i].end());
ok1 &= (ed[i].size() == 2 || ed[i].empty());
}
sub1();
}
int main(){
ios_base::sync_with_stdio(0);
cin.tie(NULL);
cout.tie(NULL);
//cin >> tc;
while(tc--){
input();
solve();
}
}
# | 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... |