oj.uz

Submission #787256

# Submission time Handle Problem Language Result Execution time Memory
787256 2023-07-19T00:46:49 Z trucmai Ball Machine (BOI13_ballmachine) C++17
100 / 100
 144 ms 54892 KB 
//i_love_aisukiuwu
#include <bits/stdc++.h>
using namespace std;

#ifdef LOCAL
  #include "/home/trucmai/.vim/tools.h"
  #define debug(x...) cerr << "\e[91m"<<__func__<<":"<<__LINE__<<" [" << #x << "] = ["; _print(x); cerr << "\e[39m" << endl;
  #else
  #define debug(x...)
#endif

void open(){
  if(fopen("i.inp","r")){
    freopen("i.inp","r",stdin);
    freopen("o.out","w",stdout);
  }
}

#define ll long long
#define all(a) (a).begin(), (a).end()
#define vi vector<ll>
#define pi pair<ll,ll>
#define pii pair<ll,pair<ll,ll>>
#define fi first
#define se second
#define gcd __gcd
#define mset(a,v) memset(a, v, sizeof(a))
#define endl '\n'
#define spc " "

const int MN1 = 1e6 + 5,MN2 = 1e4 + 5,LOG = 20;
const ll MOD = 1e9 + 7,INF = 1e9;
ll n,q;
ll mx[MN1],h[MN1],tin[MN1];
ll up[MN1][LOG];
bool col[MN1];
vector<ll>adj[MN1]; 
priority_queue<pi,vector<pi>,greater<pi>>pq;

void dfs(ll u){
  mx[u] = u;
  for(ll v : adj[u]){
    h[v] = h[u] + 1;
    up[v][0] = u;
    dfs(v);
    mx[u] = min(mx[u],mx[v]);
  }
}

ll timer = 0;
void dfs2(ll u){
  for(ll v : adj[u]) dfs2(v);
  tin[u] = ++timer; 
}

void solve(){
  cin>>n>>q; 
  for(ll i = 1,p;i <= n;++i){
    cin>>p;
    adj[p].push_back(i);
  }
  dfs(0);
  for(ll i = 1;i < LOG;++i)
    for(ll j = 1;j <= n;++j) up[j][i] = up[up[j][i-1]][i-1];
  for(ll i = 1;i <= n;++i)
    sort(all(adj[i]),[&](ll x,ll y){return mx[x] < mx[y];});
  dfs2(0);
  for(ll i = 1;i <= n;++i){
    // cout<<"DEBUG: "<<i<<spc<<tin[i]<<endl;
    pq.push({tin[i],i}); 
  }
  while(q--){
    ll t,u; cin>>t>>u; 
    if(t == 1){
      ll ptr = 0;
      while(u--){
        ptr = pq.top().se; pq.pop();
        //cout<<"DEBUG: "<<ptr<<endl;
        col[ptr] = true;   
      }
      cout<<ptr<<endl;
    } 
    else{
      ll v = u; 
      for(ll i = LOG-1;i >= 0;--i)
        if(col[up[v][i]]) v = up[v][i]; 
      col[v] = false;
      pq.push({tin[v],v});
      cout<<h[u] - h[v]<<endl;
    }
  }
}

signed main(){
  cin.tie(0) -> sync_with_stdio(0);
  open();
  ll t = 1; //cin>>t;
  while(t--) solve(); 
  //cerr << endl << "Time elapsed: " << 1.0 * clock() / CLOCKS_PER_SEC << " s.\n";
}

Compilation message

ballmachine.cpp: In function 'void open()':
ballmachine.cpp:14:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   14 |     freopen("i.inp","r",stdin);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~
ballmachine.cpp:15:12: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   15 |     freopen("o.out","w",stdout);
      |     ~~~~~~~^~~~~~~~~~~~~~~~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23892 KB Output is correct
2 Correct 84 ms 39180 KB Output is correct
3 Correct 57 ms 39088 KB Output is correct
4 Correct 12 ms 23764 KB Output is correct
5 Correct 14 ms 23804 KB Output is correct
6 Correct 12 ms 24064 KB Output is correct
7 Correct 12 ms 24076 KB Output is correct
8 Correct 12 ms 24020 KB Output is correct
9 Correct 16 ms 24844 KB Output is correct
10 Correct 26 ms 27716 KB Output is correct
11 Correct 80 ms 39168 KB Output is correct
12 Correct 73 ms 39100 KB Output is correct
13 Correct 75 ms 39108 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 30068 KB Output is correct
2 Correct 129 ms 50340 KB Output is correct
3 Correct 71 ms 46228 KB Output is correct
4 Correct 54 ms 32476 KB Output is correct
5 Correct 55 ms 32328 KB Output is correct
6 Correct 53 ms 32220 KB Output is correct
7 Correct 54 ms 31292 KB Output is correct
8 Correct 40 ms 30136 KB Output is correct
9 Correct 144 ms 50764 KB Output is correct
10 Correct 121 ms 50320 KB Output is correct
11 Correct 103 ms 50304 KB Output is correct
12 Correct 135 ms 48220 KB Output is correct
13 Correct 100 ms 50924 KB Output is correct
14 Correct 70 ms 46328 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 37416 KB Output is correct
2 Correct 127 ms 48960 KB Output is correct
3 Correct 117 ms 48552 KB Output is correct
4 Correct 94 ms 45544 KB Output is correct
5 Correct 87 ms 45232 KB Output is correct
6 Correct 84 ms 45156 KB Output is correct
7 Correct 91 ms 43956 KB Output is correct
8 Correct 109 ms 48716 KB Output is correct
9 Correct 122 ms 50860 KB Output is correct
10 Correct 124 ms 50556 KB Output is correct
11 Correct 128 ms 50488 KB Output is correct
12 Correct 133 ms 49016 KB Output is correct
13 Correct 144 ms 54892 KB Output is correct
14 Correct 103 ms 46740 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 134 ms 51080 KB Output is correct
2 Correct 128 ms 48936 KB Output is correct
3 Correct 89 ms 54500 KB Output is correct
4 Correct 129 ms 50980 KB Output is correct
5 Correct 124 ms 50564 KB Output is correct
6 Correct 108 ms 50572 KB Output is correct
7 Correct 122 ms 48900 KB Output is correct
8 Correct 92 ms 54460 KB Output is correct
9 Correct 74 ms 46388 KB Output is correct