Submission #524412

#	Time	Username	Problem	Language	Result	Execution time	Memory
524412		IMystic	Ball Machine (BOI13_ballmachine)	C++17	16.23 / 100	1101 ms	28344 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int N = 100010, INF = 1000000000;
vector<int> adj[N];
vector<int> pref(N, INF), dist(N, INF);
vector<pair<int, bool>> order;

int lg = 1;
void dfs(int n, int par){
    sort(adj[n].begin(), adj[n].end(), [](int a, int b){return pref[a] < pref[b];});
    if(par != -1)dist[n] = dist[par] + 1;
    lg = max(lg, dist[n]);
    for(int c : adj[n]){
        if(c != par){
            dfs(c, n);
        }
    }
    order.emplace_back(n, false);
}

int main(){
    ios_base :: sync_with_stdio(false);
    cin.tie(nullptr);

    int n, m, root;
    cin >> n >> m;
    vector<int> p(n);
    for(int i=0; i<n; i++){
        cin >> p[i];
        --p[i];
        if(p[i] != -1){
            adj[i].push_back(p[i]);
            adj[p[i]].push_back(i);
        }else root = i;
    }
    
    {   
        int c = 0;
        for(int i=0; i<n; i++){
            int curr = 0;
            while(curr != -1){
                if(pref[curr] < c)break;
                pref[curr] = c;
                curr = p[curr];
            }
            ++c;
        }
    }
    
    vector<int> id(n);
    dist[root] = 0;
    dfs(root, -1);
    for(int i=0; i<n; i++)id[order[i].first] = i;

    set<int> tofill;
    for(int i=0; i<n; i++)tofill.insert(i);

    lg = 32 - __builtin_clz(lg + 1);
    vector<int> B[lg];
    {   
        B[0].resize(n);
        B[0][root] = root;
        for(int i=0; i<n; i++)if(p[i] != -1)B[0][i] = p[i];
        for(int c=1; c<lg; c++){
            B[c].resize(n);
            for(int i=0; i<n; i++){
                B[c][i] = B[c-1][B[c-1][i]];
            }
        }
    }
    p[root] = root;
    for(int i=0; i<m; i++){
        int t, x;
        cin >> t >> x;
        if(t & 1){
            vector<int> tem;
            auto it = tofill.begin();
            while(x--){
                assert(it != tofill.end());
                order[*it].second = true;
                tem.push_back(*it);
                ++it;
            }
            cout << order[tem.back()].first + 1 << '\n';
            for(int &c : tem)tofill.erase(c);
        }else {
            --x;
            int y = x;
            while(y != p[y] && order[id[p[y]]].second)y = p[y];
            // for(int i = lg - 1; i>=0; i--){
            //     if(order[B[i][y]].second)y = B[i][y];
            // }
           // cout << y << '\n';
            order[id[y]].second = false;
            tofill.insert(id[y]);
            cout << dist[x] - dist[y] << '\n';
        }
    }

    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'int main()':
ballmachine.cpp:73:13: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
   73 |     p[root] = root;

• Subtask 1: 3.8461538461538463 / 25
• Subtask 2: 10.714285714285714 / 30
• Subtask 3: 0 / 40
• Subtask 4: 1.6666666666666667 / 5