oj.uz

Submission #157461

# Submission time Handle Problem Language Result Execution time Memory
157461 2019-10-11T16:02:07 Z GoldNextYear Ball Machine (BOI13_ballmachine) C++14
100 / 100
 869 ms 28108 KB 
#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.0 / 25.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2936 KB Output is correct
2 Correct 661 ms 14712 KB Output is correct
3 Correct 459 ms 13776 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 5 ms 2808 KB Output is correct
6 Correct 7 ms 2936 KB Output is correct
7 Correct 11 ms 2936 KB Output is correct
8 Correct 11 ms 2936 KB Output is correct
9 Correct 47 ms 3448 KB Output is correct
10 Correct 130 ms 5624 KB Output is correct
11 Correct 649 ms 14724 KB Output is correct
12 Correct 456 ms 13856 KB Output is correct
13 Correct 613 ms 14132 KB Output is correct

Subtask #2
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 343 ms 7668 KB Output is correct
2 Correct 825 ms 24004 KB Output is correct
3 Correct 530 ms 19188 KB Output is correct
4 Correct 495 ms 9548 KB Output is correct
5 Correct 489 ms 9748 KB Output is correct
6 Correct 475 ms 9240 KB Output is correct
7 Correct 482 ms 8804 KB Output is correct
8 Correct 341 ms 7616 KB Output is correct
9 Correct 732 ms 23884 KB Output is correct
10 Correct 834 ms 23868 KB Output is correct
11 Correct 761 ms 23052 KB Output is correct
12 Correct 777 ms 21724 KB Output is correct
13 Correct 557 ms 23544 KB Output is correct
14 Correct 525 ms 19332 KB Output is correct

Subtask #3
40.0 / 40.0

# Verdict Execution time Memory Grader output
1 Correct 374 ms 13912 KB Output is correct
2 Correct 825 ms 23168 KB Output is correct
3 Correct 529 ms 22904 KB Output is correct
4 Correct 520 ms 20352 KB Output is correct
5 Correct 512 ms 20344 KB Output is correct
6 Correct 558 ms 20396 KB Output is correct
7 Correct 519 ms 19164 KB Output is correct
8 Correct 535 ms 22996 KB Output is correct
9 Correct 819 ms 24952 KB Output is correct
10 Correct 804 ms 24912 KB Output is correct
11 Correct 833 ms 24936 KB Output is correct
12 Correct 833 ms 23276 KB Output is correct
13 Correct 850 ms 28108 KB Output is correct
14 Correct 728 ms 21568 KB Output is correct

Subtask #4
5.0 / 5.0

# Verdict Execution time Memory Grader output
1 Correct 869 ms 23992 KB Output is correct
2 Correct 786 ms 22740 KB Output is correct
3 Correct 537 ms 25936 KB Output is correct
4 Correct 856 ms 24184 KB Output is correct
5 Correct 781 ms 24184 KB Output is correct
6 Correct 748 ms 22968 KB Output is correct
7 Correct 796 ms 23032 KB Output is correct
8 Correct 560 ms 25700 KB Output is correct
9 Correct 510 ms 19208 KB Output is correct