oj.uz

답안 #971236

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
971236 2024-04-28T08:14:20 Z kebine Ball Machine (BOI13_ballmachine) C++17
0 / 100
 177 ms 9340 KB 
#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.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 1 ms 4696 KB Output isn't correct
2 Incorrect 147 ms 6584 KB Output isn't correct
3 Incorrect 135 ms 6800 KB Output isn't correct
4 Incorrect 2 ms 4696 KB Output isn't correct
5 Incorrect 2 ms 4700 KB Output isn't correct
6 Incorrect 2 ms 4700 KB Output isn't correct
7 Incorrect 3 ms 4700 KB Output isn't correct
8 Incorrect 3 ms 4700 KB Output isn't correct
9 Incorrect 11 ms 4700 KB Output isn't correct
10 Incorrect 29 ms 4952 KB Output isn't correct
11 Incorrect 140 ms 6532 KB Output isn't correct
12 Incorrect 177 ms 6816 KB Output isn't correct
13 Incorrect 164 ms 6460 KB Output isn't correct

Subtask #2
0 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 5 ms 5208 KB Output isn't correct
2 Incorrect 24 ms 7404 KB Output isn't correct
3 Incorrect 18 ms 7124 KB Output isn't correct
4 Incorrect 7 ms 5528 KB Output isn't correct
5 Incorrect 5 ms 5464 KB Output isn't correct
6 Incorrect 5 ms 5464 KB Output isn't correct
7 Incorrect 5 ms 5468 KB Output isn't correct
8 Incorrect 3 ms 5212 KB Output isn't correct
9 Incorrect 14 ms 7772 KB Output isn't correct
10 Incorrect 14 ms 7516 KB Output isn't correct
11 Incorrect 14 ms 7516 KB Output isn't correct
12 Incorrect 16 ms 7516 KB Output isn't correct
13 Incorrect 12 ms 8036 KB Output isn't correct
14 Incorrect 18 ms 7124 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 7 ms 6236 KB Output isn't correct
2 Incorrect 20 ms 7516 KB Output isn't correct
3 Incorrect 12 ms 7768 KB Output isn't correct
4 Incorrect 15 ms 7240 KB Output isn't correct
5 Incorrect 11 ms 6948 KB Output isn't correct
6 Incorrect 13 ms 6804 KB Output isn't correct
7 Incorrect 12 ms 7004 KB Output isn't correct
8 Incorrect 13 ms 8340 KB Output isn't correct
9 Incorrect 17 ms 8528 KB Output isn't correct
10 Incorrect 14 ms 8280 KB Output isn't correct
11 Incorrect 14 ms 8256 KB Output isn't correct
12 Incorrect 24 ms 8360 KB Output isn't correct
13 Incorrect 19 ms 9332 KB Output isn't correct
14 Incorrect 17 ms 7844 KB Output isn't correct

Subtask #4
0 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 19 ms 8576 KB Output isn't correct
2 Incorrect 15 ms 8284 KB Output isn't correct
3 Incorrect 13 ms 9340 KB Output isn't correct
4 Incorrect 16 ms 8676 KB Output isn't correct
5 Incorrect 16 ms 8340 KB Output isn't correct
6 Incorrect 16 ms 8360 KB Output isn't correct
7 Incorrect 18 ms 8284 KB Output isn't correct
8 Incorrect 14 ms 9308 KB Output isn't correct
9 Incorrect 13 ms 7692 KB Output isn't correct