oj.uz

Submission #126399

# Submission time Handle Problem Language Result Execution time Memory
126399 2019-07-07T15:29:19 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 1000 ms 25320 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;
    for(int i = 1;i<=n;i++){
        int x;
        cin>>x;
        if(!x) x = -1;
        par[i] = x;
        if(x == -1) continue;
        g[i].push_back({0,x});
        g[x].push_back({0,i});
    }
    memset(d,-1,sizeof(d));
    dfs(1);
    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(1);
   // 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;
    }*/

    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;
            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:96:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<all.size();i++){
                   ~^~~~~~~~~~~
ballmachine.cpp:135:25: warning: unused variable 'c' [-Wunused-variable]
                     int c = pq.size();
                         ^
ballmachine.cpp:130:18: warning: unused variable 'f' [-Wunused-variable]
             bool f = false;
                  ^

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Incorrect 13 ms 12536 KB Output isn't correct
2 Incorrect 363 ms 17904 KB Output isn't correct
3 Incorrect 349 ms 17892 KB Output isn't correct
4 Incorrect 13 ms 12408 KB Output isn't correct
5 Incorrect 13 ms 12536 KB Output isn't correct
6 Incorrect 14 ms 12536 KB Output isn't correct
7 Incorrect 16 ms 12536 KB Output isn't correct
8 Incorrect 16 ms 12536 KB Output isn't correct
9 Incorrect 39 ms 12920 KB Output isn't correct
10 Incorrect 82 ms 13816 KB Output isn't correct
11 Incorrect 365 ms 17776 KB Output isn't correct
12 Incorrect 342 ms 17780 KB Output isn't correct
13 Incorrect 357 ms 17692 KB Output isn't correct

Subtask #2
6.42857142857 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 15240 KB Output is correct
2 Execution timed out 1070 ms 21896 KB Time limit exceeded
3 Incorrect 363 ms 19552 KB Output isn't correct
4 Incorrect 371 ms 15960 KB Output isn't correct
5 Incorrect 893 ms 16460 KB Output isn't correct
6 Execution timed out 1060 ms 16128 KB Time limit exceeded
7 Incorrect 498 ms 15620 KB Output isn't correct
8 Correct 250 ms 15348 KB Output is correct
9 Incorrect 407 ms 23020 KB Output isn't correct
10 Execution timed out 1075 ms 21736 KB Time limit exceeded
11 Incorrect 404 ms 22000 KB Output isn't correct
12 Incorrect 616 ms 22540 KB Output isn't correct
13 Correct 380 ms 23536 KB Output is correct
14 Incorrect 360 ms 19436 KB Output isn't correct

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1058 ms 17656 KB Time limit exceeded
2 Execution timed out 1072 ms 21992 KB Time limit exceeded
3 Execution timed out 1079 ms 22388 KB Time limit exceeded
4 Execution timed out 1078 ms 21236 KB Time limit exceeded
5 Execution timed out 1065 ms 20340 KB Time limit exceeded
6 Execution timed out 1069 ms 21108 KB Time limit exceeded
7 Execution timed out 1058 ms 20080 KB Time limit exceeded
8 Execution timed out 1074 ms 22512 KB Time limit exceeded
9 Execution timed out 1063 ms 23028 KB Time limit exceeded
10 Execution timed out 1037 ms 21740 KB Time limit exceeded
11 Execution timed out 1063 ms 22700 KB Time limit exceeded
12 Execution timed out 1061 ms 21772 KB Time limit exceeded
13 Execution timed out 1080 ms 25320 KB Time limit exceeded
14 Incorrect 385 ms 19372 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 23008 KB Time limit exceeded
2 Execution timed out 1080 ms 21488 KB Time limit exceeded
3 Correct 392 ms 24796 KB Output is correct
4 Execution timed out 1077 ms 23108 KB Time limit exceeded
5 Execution timed out 1073 ms 21736 KB Time limit exceeded
6 Incorrect 513 ms 22416 KB Output isn't correct
7 Execution timed out 1085 ms 21556 KB Time limit exceeded
8 Correct 403 ms 24668 KB Output is correct
9 Incorrect 368 ms 19540 KB Output isn't correct