Submission #673832

#	Time	Username	Problem	Language	Result	Execution time	Memory
673832		Cookie	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	163 ms	30740 KiB

ballmachine

#include<bits/stdc++.h>

#include<fstream>

using namespace std;
ifstream fin("INTERNET.INP");
ofstream fout("INTERNET.OUT");
#define ll long long
#define vt vector
#define pb push_back
#define fi first
#define se second
#define forr(i, a, b) for(int i = a; i < b; i++)
#define dorr(i, a, b) for(int i = a; i >= b; i--)
#define pii pair<int, int>
#define pll pair<ll, ll>
#define int long long
const int mxn = 1e5, sq = 300, mxv = 1e4;
const int inf = 1e9;
int n, q, root;
vt<int>adj[mxn + 1];
int pos[mxn + 1], t = 1, dep[mxn + 1], mn[mxn + 1];
int up[mxn  +1][17];
bool used[mxn + 1];
void dfs2(int s, int pre){
    mn[s] = s;
    for(auto i: adj[s]){
        if(i != pre){
            dfs2(i, s);
            mn[s] = min(mn[s], mn[i]);
        }
    }
}
bool cmp2(int a, int b){
    return(mn[a] < mn[b]);
}
void dfs(int s, int pre){
    sort(adj[s].begin(), adj[s].end(), cmp2);
    for(auto i: adj[s]){
        if(i != pre){
            dep[i] = dep[s] + 1;
            dfs(i, s); up[i][0] = s;
        }
    }
    pos[s] = t++;
}
struct cmp{
    bool operator ()(int a, int b){
        return(pos[a] > pos[b]);
    }
};
priority_queue<int, vt<int>, cmp>pq;
int lift(int x){
    int ans = x;
    for(int i = 16; i >= 0; i--){
        if(up[ans][i] && used[up[ans][i]]){
            ans = up[ans][i];
        }
    }
    return(ans);
}
signed main()
{
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
    cin >> n >> q;
    for(int i = 1; i <= n; i++){
        int v; cin >> v;
        if(!v)root = i;
        else adj[v].pb(i);
    }
    dfs2(root, -1);
    dfs(root, -1);
    used[0] = true; //avoid mistake
    for(int i = 1; i <= n; i++){
        pq.push(i); used[i] = false;
    }
    for(int i = 1; i < 17; i++){
        for(int j = 1; j <= n; j++){
            up[j][i] = up[up[j][i - 1]][i - 1];
        }
    }
    for(int i = 0; i < q; i++){
        int idq; cin >> idq;
        if(idq == 1){
            int k; cin >> k;
            int cr;
            for(int j = 0; j < k; j++){
                cr = pq.top(); pq.pop(); used[cr] = true; 
            }
            cout << cr << "\n";
        }else{
            int x; cin >> x;
            int highest = lift(x); pq.push(highest); used[highest] = false;
            cout << dep[x] - dep[highest] << "\n";
        }
    }
    return 0;
}

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