Submission #162926

#	Time	Username	Problem	Language	Result	Execution time	Memory
162926		MvC	Cat in a tree (BOI17_catinatree)	C++11	100 / 100	907 ms	409868 KiB

catinatree

#pragma GCC target("avx2")
#pragma GCC optimization("O3")
#pragma GCC optimization("unroll-loops")
#include <bits/stdc++.h>
#define rc(x) return cout<<x<<endl,0
#define pb push_back
#define mkp make_pair
#define in insert
#define er erase
#define fd find
#define fr first
#define sc second
typedef long long ll;
typedef long double ld;
const ll INF=0x3f3f3f3f3f3f3f3f;
const ll llinf=(1LL<<62);
const int inf=(1<<30);
const int nmax=2e5+50;
const int mod=1e9+7;
using namespace std;
int n,k,v[nmax],f[nmax][500],x,y,i,sf[nmax],pr[nmax],r,rs,sz[nmax];
vector<int>a[nmax];
void dfs(int x)
{
	int sm=0;
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		dfs(y);
		sm+=f[y][k-1];
	}
	f[x][0]=1+sm;
	for(int i=1;i<=k;i++)
	{
		for(int j=0;j<(int)a[x].size();j++)
		{
			int y=a[x][j];
			pr[j]=f[y][max(i-1,k-i-1)];
			if(j)pr[j]+=pr[j-1];
		}
		for(int j=(int)a[x].size()-1;j>=0;j--)
		{
			int y=a[x][j];
			sf[j]=f[y][max(i-1,k-i-1)];
			if(j<(int)a[x].size()-1)sf[j]+=sf[j+1];
		}
		for(int j=0;j<(int)a[x].size();j++)
		{
			int y=a[x][j];
			sm=f[y][i-1];
			if(j)sm+=pr[j-1];
			if(j<(int)a[x].size()-1)sm+=sf[j+1];
			f[x][i]=max(f[x][i],sm);
		}
	}
	for(int i=k;i>=0;i--)f[x][i]=max(f[x][i],f[x][i+1]);
}
void rfs(int x)
{
	sz[x]=1;
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		rfs(y);
	}
	for(int j=0;j<=r;j++)f[x][j]=-inf;
	f[x][1]=0;
	f[x][0]=inf;
	for(int i=0;i<(int)a[x].size();i++)
	{
		int y=a[x][i];
		for(int j=min(sz[x],r);j>=0;j--)
		{
			for(int t=0;t<=min(sz[y],r-j);t++)
			{
				if(f[x][j]+f[y][t]+1>=k)
				{
					f[x][j+t]=max(f[x][j+t],min(f[x][j],f[y][t]+1));
				}
			}
		}
		sz[x]+=sz[y];
	}
}
int main()
{
	//freopen("sol.in","r",stdin);
	//freopen("sol.out","w",stdout);
	//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
	ios_base::sync_with_stdio(false);cin.tie(0);cerr.tie(0);cout.tie(0);
	cin>>n>>k;
	for(i=2;i<=n;i++)
	{
		cin>>x;
		x++;
		a[x].pb(i);
	}
	if(k*k<=n)
	{
		dfs(1);
		rs=f[1][0];
	}
	else
	{
		r=n/k+1;
		rfs(1);
		for(i=0;i<=r;i++)if(f[1][i]>=0)rs=i;
	}
	cout<<rs<<endl;
	return 0;
}

Compilation message (stderr)

catinatree.cpp:2:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("O3")
 
catinatree.cpp:3:0: warning: ignoring #pragma GCC optimization [-Wunknown-pragmas]
 #pragma GCC optimization("unroll-loops")

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