oj.uz

답안 #126386

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
126386 2019-07-07T15:07:26 Z Vardanyan Ball Machine (BOI13_ballmachine) C++14
7.53968 / 100
 1000 ms 28912 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;
            /*if(k>ms.size()){
                cout<<k<< " "<<ms.size()<<endl;
                system("pause");
            }*/
            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: 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

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1075 ms 12536 KB Time limit exceeded
2 Execution timed out 1088 ms 19956 KB Time limit exceeded
3 Incorrect 367 ms 20212 KB Output isn't correct
4 Execution timed out 1082 ms 12536 KB Time limit exceeded
5 Execution timed out 1084 ms 12536 KB Time limit exceeded
6 Incorrect 15 ms 12536 KB Output isn't correct
7 Execution timed out 1087 ms 12536 KB Time limit exceeded
8 Execution timed out 1088 ms 12536 KB Time limit exceeded
9 Execution timed out 1090 ms 12920 KB Time limit exceeded
10 Execution timed out 1087 ms 14328 KB Time limit exceeded
11 Execution timed out 1086 ms 19828 KB Time limit exceeded
12 Incorrect 370 ms 20084 KB Output isn't correct
13 Execution timed out 1080 ms 19928 KB Time limit exceeded

Subtask #2
6.42857142857 / 30.0

# 결과 실행 시간 메모리 Grader output
1 Correct 270 ms 15868 KB Output is correct
2 Execution timed out 1080 ms 25580 KB Time limit exceeded
3 Incorrect 387 ms 23404 KB Output isn't correct
4 Execution timed out 1093 ms 16848 KB Time limit exceeded
5 Execution timed out 1090 ms 16632 KB Time limit exceeded
6 Execution timed out 1083 ms 17140 KB Time limit exceeded
7 Execution timed out 1085 ms 16248 KB Time limit exceeded
8 Correct 265 ms 15864 KB Output is correct
9 Incorrect 454 ms 26740 KB Output isn't correct
10 Execution timed out 1093 ms 25456 KB Time limit exceeded
11 Incorrect 429 ms 25840 KB Output isn't correct
12 Execution timed out 1083 ms 25844 KB Time limit exceeded
13 Correct 421 ms 26740 KB Output is correct
14 Incorrect 390 ms 23424 KB Output isn't correct

Subtask #3
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1079 ms 19352 KB Time limit exceeded
2 Execution timed out 1082 ms 25712 KB Time limit exceeded
3 Execution timed out 1085 ms 25204 KB Time limit exceeded
4 Execution timed out 1079 ms 24052 KB Time limit exceeded
5 Execution timed out 1058 ms 23212 KB Time limit exceeded
6 Execution timed out 1082 ms 23924 KB Time limit exceeded
7 Execution timed out 1080 ms 23028 KB Time limit exceeded
8 Execution timed out 1081 ms 25204 KB Time limit exceeded
9 Execution timed out 1085 ms 26868 KB Time limit exceeded
10 Execution timed out 1081 ms 25456 KB Time limit exceeded
11 Execution timed out 1082 ms 26348 KB Time limit exceeded
12 Execution timed out 1081 ms 25584 KB Time limit exceeded
13 Execution timed out 1093 ms 28912 KB Time limit exceeded
14 Incorrect 480 ms 23152 KB Output isn't correct

Subtask #4
1.11111111111 / 5.0

# 결과 실행 시간 메모리 Grader output
1 Execution timed out 1070 ms 26844 KB Time limit exceeded
2 Execution timed out 1074 ms 25348 KB Time limit exceeded
3 Correct 448 ms 28528 KB Output is correct
4 Execution timed out 1092 ms 26864 KB Time limit exceeded
5 Execution timed out 1074 ms 25348 KB Time limit exceeded
6 Incorrect 556 ms 26092 KB Output isn't correct
7 Execution timed out 1083 ms 25200 KB Time limit exceeded
8 Correct 438 ms 28420 KB Output is correct
9 Incorrect 397 ms 23404 KB Output isn't correct