Submission #157461

#	Time	Username	Problem	Language	Result	Execution time	Memory
157461		GoldNextYear	Ball Machine (BOI13_ballmachine)	C++14	100 / 100	869 ms	28108 KiB

ballmachine

#define fast ios_base::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#include <bits/stdc++.h>
using namespace std;
#define sqr 340
#define mid (l+r)/2
#define pb push_back
#define ppb pop_back
#define fi first
#define se second
#define lb lower_bound
#define ub upper_bound
#define ins insert
#define era erase
#define C continue
#define mem(dp,i) memset(dp,i,sizeof(dp))
#define mset multiset
typedef long long ll;
typedef long double ld;
typedef pair<int,int> pi;
typedef pair<ll,ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<pi> vpi;
typedef vector<pll> vpll;
const ll mod=1000000007;
const ll mod2=998244353;
const ll inf=1e18*4;
const ld pai=acos(-1);
int n,q,root,timer1,timer2,ans;
vi v[100009];
int least[100009],w[100009],dp[100009][20];
int a1[100009],a2[100009],id1[100009],id2[100009],st[100009],en[100009];
int tree1[400009],tree2[400009],lzy[400009];
bool cmp(int a,int b){
        return least[a]<least[b];
}
void dfs1(int node,int p){
        w[node]=w[p]+1;
        least[node]=node;
        for(auto u:v[node]){
                if(u==p)C;
                dfs1(u,node);
                least[node]=min(least[node],least[u]);
        }
}
void dfs2(int node,int p){
        dp[node][0]=p;
        a2[timer2]=node;
        id2[node]=timer2;
        st[node]=timer2++;
        for(auto u:v[node]){
                if(u==p)C;
                dfs2(u,node);
        }
        a1[timer1]=node;
        id1[node]=timer1++;
        en[node]=timer2-1;
}
void lzyUPD(int node,int l,int r){
        if(lzy[node]==0)return;
        tree2[node]=lzy[node];
        if(l!=r){
                lzy[node*2]=lzy[node*2+1]=lzy[node];
        }
        lzy[node]=0;
}
void build(int node,int l,int r){
        if(l==r){
                tree1[node]=1;
                return;
        }
        build(node*2,l,mid);
        build(node*2+1,mid+1,r);
        tree1[node]=max(tree1[node*2],tree1[node*2+1]);
}
int query1(int node,int l,int r,int s,int e){
        if(s<=l && e>=r)return tree1[node];
        if(s<=mid && e>=mid+1)return max(query1(node*2,l,mid,s,e),query1(node*2+1,mid+1,r,s,e));
        else if(s<=mid)return query1(node*2,l,mid,s,e);
        else return query1(node*2+1,mid+1,r,s,e);
}
void upd1(int node,int l,int r,int k,int val){
        if(l==r){
                tree1[node]=val;
                return;
        }
        if(k<=mid)upd1(node*2,l,mid,k,val);
        else upd1(node*2+1,mid+1,r,k,val);
        tree1[node]=max(tree1[node*2],tree1[node*2+1]);
}
int query2(int node,int l,int r,int k){
        lzyUPD(node,l,r);
        if(l==r)return tree2[node];
        if(k<=mid)return query2(node*2,l,mid,k);
        else return query2(node*2+1,mid+1,r,k);
}
void upd2(int node,int l,int r,int s,int e,int x){
        lzyUPD(node,l,r);
        if(s<=l && e>=r){
                lzy[node]=x;
                lzyUPD(node,l,r);
                return;
        }
        if(s<=mid)upd2(node*2,l,mid,s,e,x);
        if(e>=mid+1)upd2(node*2+1,mid+1,r,s,e,x);
}
void bin(){
        int l=-1,r=n;
        while(r-l>1){
                if(query1(1,0,n-1,0,mid)==1)r=mid;
                else l=mid;
        }
        ans=a1[r];
        upd1(1,0,n-1,r,0);
        upd2(1,0,n-1,st[ans],en[ans],w[ans]);
}
void fill(){
        for(int j=1;j<20;j++){
                for(int i=0;i<n;i++){
                        dp[i][j]=dp[dp[i][j-1]][j-1];
                }
        }
}
int solve(int node,int k){
        int l=w[node]-k;
        for(int i=0;i<20;i++){
                if((l&(1<<i)))node=dp[node][i];
        }
        return node;
}
int main(){
        cin>>n>>q;
        for(int i=0;i<n;i++){
                int x;cin>>x,x--;
                if(x==-1){root=i;C;}
                v[x].pb(i);
                v[i].pb(x);
        }
        dfs1(root,root);
        for(int i=0;i<n;i++)sort(v[i].begin(),v[i].end(),cmp);
        dfs2(root,root);
        build(1,0,n-1);
        fill();
        while(q--){
                int t;cin>>t;
                if(t==1){
                        int k;cin>>k;
                        while(k--){
                                bin();
                        }
                        cout<<ans+1<<endl;
                }
                else{
                        int node;cin>>node,node--;
                        int x=query2(1,0,n-1,id2[node]);
                        cout<<w[node]-x<<endl;
                        int xxx=solve(node,x);
                        upd1(1,0,n-1,id1[xxx],1);
                        upd2(1,0,n-1,st[xxx],en[xxx],w[xxx]+1);
                }

        }
}

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