Submission #445235

#	Time	Username	Problem	Language	Result	Execution time	Memory
445235		cpp219	Ball Machine (BOI13_ballmachine)	C++14	60.29 / 100	471 ms	51360 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[N];
vector<ll> g[N];
ll n,Q,root,x,mn[N],par[N][Log2],d[N],last,type,take[N];

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]); pq[u].push({mn[i],i});
    }
}

void Add(ll u){
    if (pq[u].empty()){
        take[u] = 1; last = u; return;
    }
    LL t = pq[u].top(); Add(t.sc);
}

ll Jump(ll node,ll step){
    //cout<<par[node][0]; exit(0);
    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 "test"
    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); last = root;
    //cout<<Jump(8,2); return 0;
    while(Q--){
        cin>>type>>x;
        if (type == 1){
            //last = 1;
            while(x--){
                if (last != root){
                    last = par[last][0]; pq[last].pop();
                }
                //cout<<last; return 0;
                Add(last);
            }
            cout<<last<<"\n";
            //cout<<take[5]; return 0;
        }
        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);
            cout<<h<<"\n";
            take[cur] = 0; //cout<<x<<" "<<h<<"\n";
            if (cur != root){
                ll p = par[cur][0]; pq[p].push({mn[cur],cur});
                if (mn[cur] < mn[last]) last = cur;
                //cout<<p<<" "<<cur<<"\n";
            }
        }
    }
}

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:51:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   51 |         freopen(task".INP","r",stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~~

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