제출 #643485

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
643485		kith14	Ball Machine (BOI13_ballmachine)	C++14	29.84 / 100	1099 ms	15956 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, 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(){
  // 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;
    // }
  }
}

bool cmp(ll a, ll b){
  return (smol[a] < smol[b]);
}

void solve(){
  bool ok1 = 1;
  buildcap(root);
  repp(i,1,n){
    sort(ed[i].begin(),ed[i].end(),cmp);
    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();
  }
}

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