oj.uz

Submission #643484

# Submission time Handle Problem Language Result Execution time Memory
643484 2022-09-22T06:58:49 Z christinelynn Ball Machine (BOI13_ballmachine) C++17
100 / 100
 166 ms 38544 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 3 ms 5076 KB Output is correct
2 Correct 86 ms 22776 KB Output is correct
3 Correct 55 ms 22500 KB Output is correct
4 Correct 2 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 3 ms 5332 KB Output is correct
8 Correct 3 ms 5332 KB Output is correct
9 Correct 7 ms 6228 KB Output is correct
10 Correct 18 ms 9496 KB Output is correct
11 Correct 87 ms 22720 KB Output is correct
12 Correct 56 ms 22460 KB Output is correct
13 Correct 75 ms 22736 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 32 ms 11224 KB Output is correct
2 Correct 116 ms 34748 KB Output is correct
3 Correct 76 ms 31524 KB Output is correct
4 Correct 45 ms 14284 KB Output is correct
5 Correct 47 ms 14104 KB Output is correct
6 Correct 45 ms 14064 KB Output is correct
7 Correct 47 ms 13064 KB Output is correct
8 Correct 31 ms 11324 KB Output is correct
9 Correct 112 ms 35340 KB Output is correct
10 Correct 129 ms 34812 KB Output is correct
11 Correct 100 ms 34836 KB Output is correct
12 Correct 109 ms 33004 KB Output is correct
13 Correct 91 ms 34244 KB Output is correct
14 Correct 76 ms 31436 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 20248 KB Output is correct
2 Correct 137 ms 33748 KB Output is correct
3 Correct 103 ms 31748 KB Output is correct
4 Correct 90 ms 29240 KB Output is correct
5 Correct 87 ms 28864 KB Output is correct
6 Correct 103 ms 28928 KB Output is correct
7 Correct 85 ms 27968 KB Output is correct
8 Correct 115 ms 31720 KB Output is correct
9 Correct 130 ms 35392 KB Output is correct
10 Correct 136 ms 35008 KB Output is correct
11 Correct 139 ms 34904 KB Output is correct
12 Correct 143 ms 33820 KB Output is correct
13 Correct 166 ms 38544 KB Output is correct
14 Correct 101 ms 31932 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 140 ms 35512 KB Output is correct
2 Correct 138 ms 33788 KB Output is correct
3 Correct 97 ms 37832 KB Output is correct
4 Correct 142 ms 35564 KB Output is correct
5 Correct 128 ms 35016 KB Output is correct
6 Correct 113 ms 34976 KB Output is correct
7 Correct 137 ms 33764 KB Output is correct
8 Correct 96 ms 37696 KB Output is correct
9 Correct 76 ms 31496 KB Output is correct