oj.uz

Submission #126406

# Submission time Handle Problem Language Result Execution time Memory
126406 2019-07-07T15:42:12 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
100 / 100
 814 ms 27368 KB 
#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

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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12540 KB Output is correct
2 Correct 603 ms 17956 KB Output is correct
3 Correct 553 ms 17928 KB Output is correct
4 Correct 12 ms 12536 KB Output is correct
5 Correct 13 ms 12664 KB Output is correct
6 Correct 16 ms 12792 KB Output is correct
7 Correct 17 ms 12664 KB Output is correct
8 Correct 18 ms 12792 KB Output is correct
9 Correct 47 ms 12920 KB Output is correct
10 Correct 130 ms 14104 KB Output is correct
11 Correct 635 ms 18032 KB Output is correct
12 Correct 556 ms 18188 KB Output is correct
13 Correct 587 ms 17776 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 287 ms 15780 KB Output is correct
2 Correct 782 ms 23560 KB Output is correct
3 Correct 710 ms 19564 KB Output is correct
4 Correct 405 ms 16196 KB Output is correct
5 Correct 378 ms 16392 KB Output is correct
6 Correct 393 ms 16328 KB Output is correct
7 Correct 385 ms 15492 KB Output is correct
8 Correct 291 ms 15604 KB Output is correct
9 Correct 760 ms 23280 KB Output is correct
10 Correct 774 ms 23656 KB Output is correct
11 Correct 776 ms 23532 KB Output is correct
12 Correct 814 ms 21360 KB Output is correct
13 Correct 580 ms 25488 KB Output is correct
14 Correct 713 ms 19560 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 347 ms 18032 KB Output is correct
2 Correct 797 ms 21612 KB Output is correct
3 Correct 484 ms 24180 KB Output is correct
4 Correct 536 ms 21360 KB Output is correct
5 Correct 611 ms 21492 KB Output is correct
6 Correct 572 ms 21364 KB Output is correct
7 Correct 565 ms 19952 KB Output is correct
8 Correct 468 ms 24200 KB Output is correct
9 Correct 754 ms 23532 KB Output is correct
10 Correct 800 ms 23680 KB Output is correct
11 Correct 808 ms 23768 KB Output is correct
12 Correct 795 ms 21868 KB Output is correct
13 Correct 695 ms 27368 KB Output is correct
14 Correct 734 ms 19564 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 808 ms 23660 KB Output is correct
2 Correct 806 ms 21796 KB Output is correct
3 Correct 587 ms 27244 KB Output is correct
4 Correct 781 ms 23792 KB Output is correct
5 Correct 787 ms 23648 KB Output is correct
6 Correct 754 ms 23660 KB Output is correct
7 Correct 790 ms 21852 KB Output is correct
8 Correct 594 ms 26928 KB Output is correct
9 Correct 723 ms 19688 KB Output is correct