제출 #126366

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
126366		Vardanyan	Ball Machine (BOI13_ballmachine)	C++14	8.63 / 100	1092 ms	28656 KiB

ballmachine

#include <bits/stdc++.h>
using namespace std;
const int N = 100*1000+5;
int par[N];
vector<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];
        if(to == p) continue;
        dfs(to,v);
        sub[v] = min(sub[v],sub[to]);
    }
}
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];
    }
   // 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};
}
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];
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;
        g[i].push_back(x);
        g[x].push_back(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];
            }
        }
    }
    vector<int> all;
    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];
            }
            cout<<ans<<endl;
        }
    }
    return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

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 'int main()':
ballmachine.cpp:73:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i = 0;i<all.size();i++){
                   ~^~~~~~~~~~~

• Subtask 1: 5.769230769230769 / 25
• Subtask 2: 0 / 30
• Subtask 3: 2.857142857142857 / 40
• Subtask 4: 0 / 5