Submission #253726

#	Time	Username	Problem	Language	Result	Execution time	Memory
253726		kimbj0709	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	790 ms	43132 KiB

ballmachine

#include<bits/stdc++.h>
using namespace std;
#define int long long
#define maxn 100050
vector<vector<int> > adj(maxn);
vector<int> mini(maxn,-1);
vector<int> fenwick(maxn,0);
vector<int> num(maxn,0);
vector<int> ipos(maxn,0);
#define f first
#define s second
int parents[18][maxn];
void add(int a){
    int pos = a+1;
    while(pos<fenwick.size()){
        fenwick[pos] += 1;
        pos += pos&(-pos);
    }
    return;
}
void add2(int a){
    int pos = a+1;
    while(pos<fenwick.size()){
        fenwick[pos] -= 1;
        pos += pos&(-pos);
    }
    return;
}
int query(int a,int b){
    int sum = 0;
    b++;
    while(b>0){
        sum += fenwick[b];
        b -= b&(-b);
    }
    while(a>0){
        sum -= fenwick[a];
        a -= a&(-a);
    }
    return sum;
}
void dfs1(int node,int parent){
    parents[0][node] = parent;
    for(auto k:adj[node]){
        if(k!=parent){
            dfs1(k,node);
        }
    }
    mini[node] = node;
    vector<pair<int,int> > vect1;
    for(auto k:adj[node]){
        if(k!=parent){
            vect1.push_back({mini[k],k});
            mini[node] = min(mini[node],mini[k]);
        }
    }
    sort(vect1.begin(),vect1.end());
    adj[node].clear();
    for(auto k:vect1){
        adj[node].push_back(k.s);
    }
}
int cnt = 1;
void dfs2(int node,int parent){
    for(auto k:adj[node]){
        if(k!=parent){
            dfs2(k,node);
        }
    }
    num[node] = cnt;
    ipos[cnt] = node;
    cnt++;
}
int find_parent(int a,int b){
    for(int i=0;i<18;i++){
        if(b&(1<<i)){
            a = parents[i][a];
        }
    }
    return a;
}
int32_t main(){
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    int no_of_vertex,no_of_query;
    int input1,input2;
    cin >> no_of_vertex >> no_of_query;
    int root = -1;
    for(int i=1;i<=no_of_vertex;i++){
        cin >> input1;
        if(input1==0){
            root = i;
        }
        else{
            adj[i].push_back(input1);
            adj[input1].push_back(i);
        }
 
    }
    memset(parents,0,sizeof(parents));
    dfs1(root,0);
    for(int i=1;i<=17;i++){
        for(int j=1;j<=no_of_vertex;j++){
            parents[i][j] = parents[i-1][parents[i-1][j]];
        }
    }
    dfs2(root,0);
    set<int> nothave;
    for(int i=1;i<=no_of_vertex;i++){
        nothave.insert(i);
    }
    vector<int> has(maxn,0);
    for(int i=0;i<no_of_query;i++){
        cin >> input1 >> input2;
        if(input1==1){//add
            int lo = 0,hi = no_of_vertex+1;
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                if(query(1,mid)+input2<=mid){
                    hi = mid;
                }
                else{
                    lo = mid;
                }
            }
            //use hi
            auto k = nothave.lower_bound(hi);
            if(*k>hi){
                k--;
            }
            cout << ipos[*k] << "\n";
            for(int j=0;j<input2;j++){
                int should = ipos[*k];
                has[should] = 1;
                add(*k);
                if(j!=input2-1){
                    k--;
                }
                nothave.erase(num[should]);
            }
        }
        else{//remove
            int lo = 0,hi = no_of_vertex+1;
            while(lo+1!=hi){
                int mid = (lo+hi)/2;
                int p = find_parent(input2,mid);
                if(has[p]==0){
                    hi = mid;
                }
                else{
                    lo = mid;
                }
            }
            /*cout << 0 << "\n";
            has[input2] = 0;
            nothave.insert(num[input2]);
            add2(num[input2]);*/
            cout << lo << "\n";
            //assert(lo==0);
            has[find_parent(input2,lo)] = 0;
            nothave.insert(num[find_parent(input2,lo)]);
            add2(num[find_parent(input2,lo)]);
        }
    }
 
 
}

Compilation message (stderr)

ballmachine.cpp: In function 'void add(long long int)':
ballmachine.cpp:15:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<fenwick.size()){
           ~~~^~~~~~~~~~~~~~~
ballmachine.cpp: In function 'void add2(long long int)':
ballmachine.cpp:23:14: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     while(pos<fenwick.size()){
           ~~~^~~~~~~~~~~~~~~

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