Submission #445258

#	Time	Username	Problem	Language	Result	Execution time	Memory
445258		cpp219	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	433 ms	24368 KiB

ballmachine

#pragma GCC optimization O2
#pragma GCC optimization "unroll-loop"
#pragma target ("avx2")

#include <bits/stdc++.h>
#define ll int
#define ld long double
#define fs first
#define sc second
using namespace std;
typedef pair<ll,ll> LL;
const ll N = 1e5 + 9;
const ll Log2 = 20;
const ll inf = 1e18 + 7;

priority_queue<LL,vector<LL>,greater<LL>> pq;
vector<ll> g[N];
ll n,Q,root,x,mn[N],par[N][Log2],d[N],last,type,take[N],pos[N];
ll nTime = 1;

void DFS(ll u){
    for (ll i = 1;i < Log2;i++) if ((1 << i) <= d[u])
        par[u][i] = par[par[u][i - 1]][i - 1];
    mn[u] = u;
    for (auto i : g[u]){
        par[i][0] = u; d[i] = d[u] + 1; DFS(i);
        mn[u] = min(mn[u],mn[i]);
    }
}

bool lf(ll x,ll y){
    return mn[x] < mn[y];
}

void geiDFS(ll u){
    sort(g[u].begin(),g[u].end(),lf);
    for (auto i : g[u]) geiDFS(i);
    pos[u] = nTime; nTime++;
}

ll Jump(ll node,ll step){
    for (ll i = Log2 - 1;i >= 0;i--){
        if (step >= (1 << i)){
            node = par[node][i]; step -= (1 << i);
        }
    }
    return node;
}

int main(){
    ios_base::sync_with_stdio(NULL); cin.tie(0); cout.tie(0);
    #define task "tst"
    if (fopen(task".INP","r")){
        freopen(task".INP","r",stdin);
        //freopen(task".OUT","w",stdout);
    }
    cin>>n>>Q;
    for (ll i = 1;i <= n;i++){
        cin>>x;
        if (x == 0) root = i;
        else g[x].push_back(i);
    }
    DFS(root); geiDFS(root);
    for (ll i = 1;i <= n;i++) pq.push({pos[i],i});
    while(Q--){
        cin>>type>>x;
        if (type == 1){
            while(x--){
                LL t = pq.top(); pq.pop();
                last = t.sc; take[t.sc] = 1;
            }
            cout<<last<<"\n";
        }
        else{
            ll l,m,h; l = 0; h = d[x];
            while(l <= h){
                m = (l + h)/2; ll nxt = Jump(x,m);
                if (!take[nxt]) h = m - 1;
                else l = m + 1;
            }
            ll cur = Jump(x,h); last = cur;
            cout<<h<<"\n"; take[cur] = 0; pq.push({pos[cur],cur});
        }
    }
}

Compilation message (stderr)

ballmachine.cpp:1: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    1 | #pragma GCC optimization O2
      | 
ballmachine.cpp:2: warning: ignoring '#pragma GCC optimization' [-Wunknown-pragmas]
    2 | #pragma GCC optimization "unroll-loop"
      | 
ballmachine.cpp:3: warning: ignoring '#pragma target ' [-Wunknown-pragmas]
    3 | #pragma target ("avx2")
      | 
ballmachine.cpp:14:21: warning: overflow in conversion from 'double' to 'int' changes value from '1.0e+18' to '2147483647' [-Woverflow]
   14 | const ll inf = 1e18 + 7;
      |                ~~~~~^~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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