oj.uz

Submission #643483

# Submission time Handle Problem Language Result Execution time Memory
643483 2022-09-22T06:58:23 Z kith14 Ball Machine (BOI13_ballmachine) C++14
100 / 100
 177 ms 38564 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 = 2e5+5, MOD = 1e9+7, LOG = 20;
ll tc = 1, n, m, ar[N], br[N], used[N];
ll x, y, k, cur = 0;
string s, s1, s2, ye = "YES", no = "NO";
ll ord[N], root, nx[N][LOG+5], dlm[N], smol[N];
vector<ll> ed[N];

void buildord(ll idx){
  for (auto i : ed[idx]){
    dlm[i] = dlm[idx]+1;
    buildord(i);
  }
  cur++;
  ord[idx] = cur;
}

void buildlift(){
  nx[root][0] = 0;
  repp(bt,1,LOG){
    repp(i,1,n){
      nx[i][bt] = nx[nx[i][bt-1]][bt-1];
    }
  }
}

void input(){
  cin >> n >> m;
  repp(i,1,n){
    cin >> ar[i];
    if (ar[i] == 0){
      if (root != 0) assert(0);
      root = i;
    }
    else{
      ed[ar[i]].pb(i);
      nx[i][0] = ar[i];
    }
  }
}

void buildsmol(ll idx){
  smol[idx] = idx;
  for (auto i : ed[idx]){
    buildsmol(i);
    smol[idx] = min(smol[idx],smol[i]);
  }
  //cout << idx << " " << smol[idx] << endl;
}

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

void solve(){
  buildsmol(root);
  repp(i,1,n){
    sort(ed[i].begin(),ed[i].end(),cmp);
  }
  buildord(root);
  buildlift();
  priority_queue<pairll, vector<pairll>, greater<pairll> > pq;
  repp(i,1,n){
    pq.push(mp(ord[i],i));
  }
  while(m--){
    cin >> x >> y;
    if (x == 1){
      ll lst;
      while(y--){
        pairll a = pq.top();
        pq.pop();
        used[a.sc] = 1;
        lst = a.sc;
      }
      cout << lst << "\n";
    }
    else if(x == 2){
      ll dis = 0, ori = y;
      repm(bt,LOG,0){
        if (used[nx[y][bt]]){
          dis += (1<<bt);
          y = nx[y][bt];
        }
      }
      used[y] = 0;
      pq.push(mp(ord[y],y));
      cout << dis << "\n";
    }
  }
}

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

Compilation message

ballmachine.cpp: In function 'void solve()':
ballmachine.cpp:94:19: warning: unused variable 'ori' [-Wunused-variable]
   94 |       ll dis = 0, ori = y;
      |                   ^~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 5076 KB Output is correct
2 Correct 80 ms 22752 KB Output is correct
3 Correct 54 ms 22472 KB Output is correct
4 Correct 3 ms 4948 KB Output is correct
5 Correct 3 ms 5076 KB Output is correct
6 Correct 3 ms 5332 KB Output is correct
7 Correct 4 ms 5332 KB Output is correct
8 Correct 3 ms 5320 KB Output is correct
9 Correct 6 ms 6232 KB Output is correct
10 Correct 16 ms 9596 KB Output is correct
11 Correct 83 ms 22848 KB Output is correct
12 Correct 59 ms 22464 KB Output is correct
13 Correct 76 ms 22748 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 30 ms 11212 KB Output is correct
2 Correct 133 ms 34764 KB Output is correct
3 Correct 72 ms 31448 KB Output is correct
4 Correct 46 ms 14276 KB Output is correct
5 Correct 57 ms 14132 KB Output is correct
6 Correct 43 ms 14148 KB Output is correct
7 Correct 45 ms 13152 KB Output is correct
8 Correct 28 ms 11252 KB Output is correct
9 Correct 127 ms 35252 KB Output is correct
10 Correct 122 ms 34888 KB Output is correct
11 Correct 113 ms 34744 KB Output is correct
12 Correct 132 ms 33028 KB Output is correct
13 Correct 90 ms 34112 KB Output is correct
14 Correct 73 ms 31420 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 54 ms 20280 KB Output is correct
2 Correct 130 ms 33832 KB Output is correct
3 Correct 107 ms 31788 KB Output is correct
4 Correct 104 ms 29220 KB Output is correct
5 Correct 93 ms 28932 KB Output is correct
6 Correct 87 ms 28908 KB Output is correct
7 Correct 98 ms 27948 KB Output is correct
8 Correct 98 ms 31684 KB Output is correct
9 Correct 141 ms 35316 KB Output is correct
10 Correct 132 ms 35064 KB Output is correct
11 Correct 145 ms 34952 KB Output is correct
12 Correct 153 ms 33892 KB Output is correct
13 Correct 177 ms 38564 KB Output is correct
14 Correct 100 ms 31916 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35504 KB Output is correct
2 Correct 128 ms 33792 KB Output is correct
3 Correct 108 ms 37652 KB Output is correct
4 Correct 141 ms 35468 KB Output is correct
5 Correct 127 ms 34992 KB Output is correct
6 Correct 132 ms 34944 KB Output is correct
7 Correct 148 ms 33832 KB Output is correct
8 Correct 101 ms 37696 KB Output is correct
9 Correct 77 ms 31496 KB Output is correct