Submission #971236

#	Time	Username	Problem	Language	Result	Execution time	Memory
971236		kebine	Ball Machine (BOI13_ballmachine)	C++17	0 / 100	177 ms	9340 KiB

ballmachine

#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());
  }
  if (ok1){
    sub1();
  }
}

int main(){
  ios_base::sync_with_stdio(0);
  cin.tie(NULL);
  cout.tie(NULL);
  //cin >> tc;
  while(tc--){
    input();
    solve();
  }
}

• Subtask 1: 0 / 25
• Subtask 2: 0 / 30
• Subtask 3: 0 / 40
• Subtask 4: 0 / 5