oj.uz

Submission #126401

# Submission time Handle Problem Language Result Execution time Memory
126401 2019-07-07T15:35:48 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
60.0794 / 100
 1000 ms 26896 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:88:7: warning: 'root' may be used uninitialized in this function [-Wmaybe-uninitialized]
     go(root);
     ~~^~~~~~

Subtask #1
25.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 12664 KB Output is correct
2 Correct 375 ms 17692 KB Output is correct
3 Correct 347 ms 17760 KB Output is correct
4 Correct 13 ms 12540 KB Output is correct
5 Correct 13 ms 12668 KB Output is correct
6 Correct 14 ms 12664 KB Output is correct
7 Correct 16 ms 12664 KB Output is correct
8 Correct 17 ms 12664 KB Output is correct
9 Correct 39 ms 12920 KB Output is correct
10 Correct 84 ms 14072 KB Output is correct
11 Correct 375 ms 17668 KB Output is correct
12 Correct 341 ms 17872 KB Output is correct
13 Correct 361 ms 17688 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 255 ms 15476 KB Output is correct
2 Correct 415 ms 23300 KB Output is correct
3 Correct 366 ms 19316 KB Output is correct
4 Correct 290 ms 15988 KB Output is correct
5 Correct 293 ms 16132 KB Output is correct
6 Correct 300 ms 16112 KB Output is correct
7 Correct 279 ms 15296 KB Output is correct
8 Correct 262 ms 15476 KB Output is correct
9 Correct 410 ms 23020 KB Output is correct
10 Correct 428 ms 23400 KB Output is correct
11 Correct 406 ms 23276 KB Output is correct
12 Correct 443 ms 21108 KB Output is correct
13 Correct 392 ms 25328 KB Output is correct
14 Correct 371 ms 19524 KB Output is correct

Subtask #3
2.85714285714 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1080 ms 18124 KB Time limit exceeded
2 Execution timed out 1089 ms 21232 KB Time limit exceeded
3 Execution timed out 1077 ms 24048 KB Time limit exceeded
4 Execution timed out 1080 ms 21108 KB Time limit exceeded
5 Execution timed out 1072 ms 21356 KB Time limit exceeded
6 Execution timed out 1085 ms 21236 KB Time limit exceeded
7 Execution timed out 1088 ms 19700 KB Time limit exceeded
8 Execution timed out 1084 ms 24052 KB Time limit exceeded
9 Execution timed out 1085 ms 22900 KB Time limit exceeded
10 Execution timed out 1059 ms 23248 KB Time limit exceeded
11 Execution timed out 1074 ms 23280 KB Time limit exceeded
12 Execution timed out 1083 ms 21356 KB Time limit exceeded
13 Execution timed out 1078 ms 26560 KB Time limit exceeded
14 Correct 386 ms 19368 KB Output is correct

Subtask #4
2.22222222222 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1070 ms 23000 KB Time limit exceeded
2 Execution timed out 1074 ms 21232 KB Time limit exceeded
3 Correct 396 ms 26860 KB Output is correct
4 Execution timed out 1078 ms 23088 KB Time limit exceeded
5 Execution timed out 1069 ms 23376 KB Time limit exceeded
6 Correct 532 ms 23408 KB Output is correct
7 Execution timed out 1071 ms 21440 KB Time limit exceeded
8 Correct 397 ms 26896 KB Output is correct
9 Correct 356 ms 19308 KB Output is correct