oj.uz

Submission #126385

# Submission time Handle Problem Language Result Execution time Memory
126385 2019-07-07T15:03:59 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
4.28571 / 100
 1000 ms 23984 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;
    set<pair<int,int> > ms;
    for(int i = 0;i<all.size();i++){
            ms.insert({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;
            while(k--){
                pair<int,int> x = *(ms.begin());
                ms.erase(ms.begin());
                used[x.second] = 1;
                if(!k){
                    cout<<x.second<<endl;
                }
            }
        }
        else{
            int x;
            cin>>x;
            int ans = 0;
            while(used[x]){
                int pr = par[x];
                if(pr == -1 || !used[pr]){
                    ms.insert({hrt[x],x});
                    used[x] = 0;
                    break;
                }
                ans++;
                x = par[x];
            }
           // 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:56:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
    for(int i = 0;i<all.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++){
                   ~^~~~~~~~~~~

Subtask #1
0 / 25.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1077 ms 12536 KB Time limit exceeded
2 Execution timed out 1084 ms 19880 KB Time limit exceeded
3 Execution timed out 1062 ms 19944 KB Time limit exceeded
4 Execution timed out 1071 ms 12408 KB Time limit exceeded
5 Execution timed out 1079 ms 12536 KB Time limit exceeded
6 Incorrect 15 ms 12664 KB Output isn't correct
7 Execution timed out 1066 ms 12664 KB Time limit exceeded
8 Execution timed out 1087 ms 12664 KB Time limit exceeded
9 Execution timed out 1082 ms 12920 KB Time limit exceeded
10 Execution timed out 1075 ms 14584 KB Time limit exceeded
11 Execution timed out 1080 ms 19956 KB Time limit exceeded
12 Execution timed out 1085 ms 19956 KB Time limit exceeded
13 Execution timed out 1079 ms 19900 KB Time limit exceeded

Subtask #2
4.28571428571 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 15992 KB Output is correct
2 Execution timed out 1072 ms 20536 KB Time limit exceeded
3 Execution timed out 1083 ms 18156 KB Time limit exceeded
4 Execution timed out 1084 ms 16912 KB Time limit exceeded
5 Execution timed out 1080 ms 16760 KB Time limit exceeded
6 Execution timed out 1086 ms 17132 KB Time limit exceeded
7 Execution timed out 1087 ms 16440 KB Time limit exceeded
8 Correct 344 ms 15864 KB Output is correct
9 Execution timed out 1082 ms 21880 KB Time limit exceeded
10 Execution timed out 1073 ms 20724 KB Time limit exceeded
11 Execution timed out 1079 ms 20656 KB Time limit exceeded
12 Execution timed out 1067 ms 20984 KB Time limit exceeded
13 Execution timed out 1073 ms 22392 KB Time limit exceeded
14 Execution timed out 1080 ms 18160 KB Time limit exceeded

Subtask #3
0 / 40.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1085 ms 19204 KB Time limit exceeded
2 Execution timed out 1083 ms 20648 KB Time limit exceeded
3 Execution timed out 1075 ms 21240 KB Time limit exceeded
4 Execution timed out 1086 ms 20096 KB Time limit exceeded
5 Execution timed out 1083 ms 19448 KB Time limit exceeded
6 Execution timed out 1085 ms 20088 KB Time limit exceeded
7 Execution timed out 1078 ms 19192 KB Time limit exceeded
8 Execution timed out 1083 ms 21284 KB Time limit exceeded
9 Execution timed out 1049 ms 21624 KB Time limit exceeded
10 Execution timed out 1087 ms 20500 KB Time limit exceeded
11 Execution timed out 1063 ms 21288 KB Time limit exceeded
12 Execution timed out 1080 ms 20776 KB Time limit exceeded
13 Execution timed out 1078 ms 23984 KB Time limit exceeded
14 Execution timed out 1077 ms 18288 KB Time limit exceeded

Subtask #4
0 / 5.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1086 ms 21604 KB Time limit exceeded
2 Execution timed out 1078 ms 20120 KB Time limit exceeded
3 Execution timed out 1080 ms 23292 KB Time limit exceeded
4 Execution timed out 1070 ms 21932 KB Time limit exceeded
5 Execution timed out 1071 ms 20488 KB Time limit exceeded
6 Execution timed out 1085 ms 21108 KB Time limit exceeded
7 Execution timed out 1082 ms 20084 KB Time limit exceeded
8 Execution timed out 1078 ms 23304 KB Time limit exceeded
9 Execution timed out 1083 ms 18408 KB Time limit exceeded