Submission #126406

#	Time	Username	Problem	Language	Result	Execution time	Memory
126406		Vardanyan	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	814 ms	27368 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
const int N = 100*1000+5;
int par[N];
vector<pair<int,int> > g[N];
int depth[N];
int d[N][25];
int sub[N];
void dfs(int v,int p = 0){
    depth[v] = depth[p]+1;
    d[v][0] = par[v];
    sub[v] = v;
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i].second;
        if(to == p) continue;
        dfs(to,v);
        sub[v] = min(sub[v],sub[to]);
        g[v][i].first = sub[to];
    }
    sort(g[v].begin(),g[v].end());
}
pair<int,int> lca(int u,int v){
    bool f = false;
    if(depth[u]>depth[v]){
            swap(u,v);
            f = true;
    }
    int dif = depth[v]-depth[u];
    for(int i = 0;i<=20;i++){
        if((dif>>i)&1) v = d[v][i];
    }
    if(u == v) return {u,u};
   // cout<<u<< " "<<v<<endl;
    for(int i = 20;i>=0;i--){
        if(d[u][i] == d[v][i]) continue;
        u = d[u][i];
        v = d[v][i];
    }
    if(f) swap(u,v);
    return {u,v};
}
vector<int> all;
bool cmp(int u,int v){
    pair<int,int> x = lca(u,v);
    if(x.first == x.second) return depth[u]>depth[v];
    return sub[x.first]<sub[x.second];
}
int hrt[N];
bool used[N];
void go(int v,int p = -1){
    for(int i = 0;i<g[v].size();i++){
        int to = g[v][i].second;
        if(to == p) continue;
        go(to,v);
    }
   /*for(int i = 0;i<all.size();i++){
    if(all[i] == v) return;
   }*/
   all.push_back(v);
}
int main(){
    ios_base::sync_with_stdio(false);
    int n,q;
    cin>>n>>q;
    int root;
    for(int i = 1;i<=n;i++){
        int x;
        cin>>x;
        if(!x) x = -1;
        par[i] = x;
        if(x == -1) {
            root = i;
            continue;
        }
        g[i].push_back({0,x});
        g[x].push_back({0,i});
    }
    memset(d,-1,sizeof(d));
    dfs(root);
    for(int k = 1;k<=20;k++){
        for(int i = 1;i<=n;i++){
            if(d[i][k-1]!=-1){
                d[i][k] = d[d[i][k-1]][k-1];
            }
        }
    }
    all.clear();
   // go(root);
   // cout<<all.size()<<endl;
    /*for(int i = 0;i<all.size();i++){
        if(all[i]>=1 && all[i]<=n) continue;
        cout<<"yyyy "<<all[i]<<endl;
    }*/
   // system("pause");
    for(int i = 1;i<=n;i++) all.push_back(i);
    sort(all.begin(),all.end(),cmp);
    //for(int i = 0;i<all.size();i++) cout<<all[i]<<" ";
    //cout<<endl;
    priority_queue<pair<int,int> > pq;
    for(int i = 0;i<all.size();i++){
            pq.push({-i,all[i]});
            hrt[all[i]] = i;
    }
    /*int x,y;
    while(cin>>x>>y){
        pair<int,int> w = lca(x,y);
        cout<<w.first<<" "<<w.second<<endl;
    }*/
    memset(used,0,sizeof(used));
    while(q--){
        int tp;
        cin>>tp;
        if(tp == 1){
            int k;
            cin>>k;
            /*if(k>ms.size()){
                cout<<k<< " "<<ms.size()<<endl;
                system("pause");
            }*/
        //    k = min(k,(int)ms.size());
            while(k--){
                pair<int,int> x = pq.top();
                pq.pop();
                used[x.second] = 1;
                if(!k){
                    cout<<x.second<<endl;
                }
            }
        }
        else{
            int x;
            cin>>x;
            int nax = x;
            int ans = 0;
            for(int i = 20;i>=0;i--){
                int u = d[x][i];
                if(u == -1) continue;
                if(!used[u]) continue;
                x = d[x][i];
            }
            used[x] = 0;
            pq.push({-hrt[x],x});
            ans = depth[nax]-depth[x];
            cout<<ans<<endl;
        }
    }
    return 0;
}

Compilation message (stderr)

ballmachine.cpp: In function 'void dfs(int, int)':
ballmachine.cpp:13:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~
ballmachine.cpp: In function 'void go(int, int)':
ballmachine.cpp:51:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<g[v].size();i++){
                   ~^~~~~~~~~~~~
ballmachine.cpp: In function 'int main()':
ballmachine.cpp:100:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<all.size();i++){
                   ~^~~~~~~~~~~
ballmachine.cpp:79:8: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     dfs(root);
     ~~~^~~~~~

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