Submission #642715

#	Time	Username	Problem	Language	Result	Execution time	Memory
642715		karrigan	Cat in a tree (BOI17_catinatree)	C++14	100 / 100	255 ms	26832 KiB

catinatree

#include<bits/stdc++.h>
using namespace std;
vector<int>a[200001];
int dep[200001];
int dep2[200001];
int in[200001];
int out[200001];
int p[200001];
int cnt=0;
void dfs(int u,int par){
in[u]=++cnt;
for (auto v:a[u]){
    if (v==par)continue;
    dep[v]=dep[u]+1;
    p[v]=u;
    dfs(v,u);
}
out[u]=cnt;
}
int st[800001];
int st2[800001];
void update(int id,int l,int r,int u,int val){
if (l>u||r<u)return;
if (l==r){
    st[id]=val;
    st2[id]=val;
    return;
}
int mid=(l+r)/2;
update(id*2,l,mid,u,val);
update(id*2+1,mid+1,r,u,val);
if (dep[st[id*2]]>dep[st[id*2+1]])st[id]=st[id*2+1];
else st[id]=st[id*2];
if (dep2[st2[id*2]]<dep2[st2[id*2+1]])st2[id]=st2[id*2+1];
else st2[id]=st2[id*2];
}
int get(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st[id];
int mid=(l+r)/2;
int t1=get(id*2,l,mid,u,v);
int t2=get(id*2+1,mid+1,r,u,v);
if (dep[t1]>dep[t2])return t2;
else return t1;
}
int get2(int id,int l,int r,int u,int v){
if (l>v||r<u||u>v)return 0;
if (u<=l&&r<=v)return st2[id];
int mid=(l+r)/2;
int t1=get2(id*2,l,mid,u,v);
int t2=get2(id*2+1,mid+1,r,u,v);
if (dep2[t1]<dep2[t2])return t2;
else return t1;
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	//freopen(".INP","r",stdin);
	//freopen(".OUT","w",stdout);
	int n,d;
	cin>>n>>d;
	for (int i=2;i<=n;i++){
        int p;
        cin>>p;
        p++;
        a[p].push_back(i);
        a[i].push_back(p);
	}
	dfs(1,0);
	dep[0]=n+1;
	for (int i=1;i<=n;i++)dep2[i]=dep[i];
	for (int i=1;i<=n;i++){
        update(1,1,n,in[i],i);
	}
	vector<int>tp;
	while (get2(1,1,n,in[1],out[1])!=0){
        auto t=get2(1,1,n,in[1],out[1]);
        update(1,1,n,in[t],0);
        tp.push_back(t);
        for (int i=0;i<d;i++){
            if (t==0)break;
            while (get(1,1,n,in[t],out[t])!=0){
                int del=get(1,1,n,in[t],out[t]);
                if (dep[del]+dep[tp.back()]-2*dep[t]>=d){
                break;
                }
                else {
                update(1,1,n,in[del],0);
                }
            }
            t=p[t];
        }
	}
	cout<<tp.size()<<'\n';
}

• Subtask 1: 11 / 11
• Subtask 2: 40 / 40
• Subtask 3: 49 / 49