oj.uz

Submission #126402

# Submission time Handle Problem Language Result Execution time Memory
126402 2019-07-07T15:37:47 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
60.0794 / 100
 1000 ms 26992 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 ans = 0;
            bool f = false;
            /*if(!used[x]){
                cout<<"yyyy"<<endl;
                system("pause");
            }*/
            while(1){
               // cout<<x<<endl;
                int pr = par[x];
                if(pr == -1 || !used[pr]){
                    int c = pq.size();
                    pq.push({-hrt[x],x});
                   /* if(c == pq.size()){
                        f = true;
                        cout<<hrt[x]<< " "<<x<<endl;
                    }*/
                    used[x] = 0;
                    break;
                }
                ans++;
                x = par[x];
            }
           /* if(f){
                cout<<"sgasdgsdgs"<<endl;
                system("pause");
            }*/
           // used[x] = 0;
           // ms.insert({hrt[x],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:143:25: warning: unused variable 'c' [-Wunused-variable]
                     int c = pq.size();
                         ^
ballmachine.cpp:134:18: warning: unused variable 'f' [-Wunused-variable]
             bool f = false;
                  ^
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 12536 KB Output is correct
2 Correct 596 ms 17600 KB Output is correct
3 Correct 546 ms 17904 KB Output is correct
4 Correct 12 ms 12664 KB Output is correct
5 Correct 13 ms 12536 KB Output is correct
6 Correct 16 ms 12664 KB Output is correct
7 Correct 17 ms 12664 KB Output is correct
8 Correct 20 ms 12664 KB Output is correct
9 Correct 46 ms 12920 KB Output is correct
10 Correct 125 ms 13992 KB Output is correct
11 Correct 574 ms 17648 KB Output is correct
12 Correct 548 ms 17776 KB Output is correct
13 Correct 597 ms 17636 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 283 ms 15476 KB Output is correct
2 Correct 763 ms 23276 KB Output is correct
3 Correct 722 ms 19392 KB Output is correct
4 Correct 349 ms 15988 KB Output is correct
5 Correct 361 ms 16036 KB Output is correct
6 Correct 348 ms 16112 KB Output is correct
7 Correct 346 ms 15296 KB Output is correct
8 Correct 279 ms 15480 KB Output is correct
9 Correct 711 ms 23152 KB Output is correct
10 Correct 746 ms 23404 KB Output is correct
11 Correct 744 ms 23400 KB Output is correct
12 Correct 739 ms 21232 KB Output is correct
13 Correct 562 ms 25200 KB Output is correct
14 Correct 723 ms 19312 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 18040 KB Time limit exceeded
2 Execution timed out 1079 ms 21360 KB Time limit exceeded
3 Execution timed out 1068 ms 24048 KB Time limit exceeded
4 Execution timed out 1066 ms 21108 KB Time limit exceeded
5 Execution timed out 1080 ms 21336 KB Time limit exceeded
6 Execution timed out 1078 ms 21364 KB Time limit exceeded
7 Execution timed out 1070 ms 19832 KB Time limit exceeded
8 Execution timed out 1080 ms 24048 KB Time limit exceeded
9 Execution timed out 1073 ms 23104 KB Time limit exceeded
10 Execution timed out 1072 ms 23220 KB Time limit exceeded
11 Execution timed out 1074 ms 23152 KB Time limit exceeded
12 Execution timed out 1086 ms 21268 KB Time limit exceeded
13 Execution timed out 1087 ms 26736 KB Time limit exceeded
14 Correct 719 ms 19436 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1081 ms 22896 KB Time limit exceeded
2 Execution timed out 1074 ms 21360 KB Time limit exceeded
3 Correct 589 ms 26992 KB Output is correct
4 Execution timed out 1090 ms 23100 KB Time limit exceeded
5 Execution timed out 1086 ms 23272 KB Time limit exceeded
6 Correct 938 ms 23280 KB Output is correct
7 Execution timed out 1074 ms 21276 KB Time limit exceeded
8 Correct 591 ms 26840 KB Output is correct
9 Correct 705 ms 19328 KB Output is correct