제출 #643482

#제출 시각아이디문제언어결과실행 시간메모리
643482kith14Ball Machine (BOI13_ballmachine)C++14
0 / 100
1096 ms16108 KiB
#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, smol[N]; 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; smol[idx] = idx; for (auto i : ed[idx]){ buildcap(i); cap[idx] += cap[i]; smol[idx] = min(smol[idx],smol[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); // repp(i,1,n){ // cout << "cap " << i << " = " << cap[i] << endl; // } while(m--){ cin >> x >> y; if (x == 1){ repp(i,1,y){ insball(root); } cout << cur << endl; } else{ roldown = 0; ll ed = 1; while(1){ if (y == root) break; if (cap[rev[y]] != used[rev[y]]){ break; } y = rev[y]; //used[y]--; if(ed) roldown++; } //cout << "stops at " << y << endl; while(1){ used[y]--; if (y == root) break; y = rev[y]; } cout << roldown << endl; } // repp(i,1,n){ // cout << "used " << i << " = " << used[i] << endl; // } } } void solve(){ bool ok1 = 1; repp(i,1,n){ if (ed[i].size() <= 1) continue; if (smol[ed[i][0]] > smol[ed[i][1]]) swap(ed[i][0],ed[i][1]); 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 timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...