oj.uz

답안 #143215

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
143215 2019-08-13T11:20:00 Z davitmarg Cat in a tree (BOI17_catinatree) C++17
0 / 100
 6 ms 5112 KB 
/*DavitMarg*/
#include <iostream>
#include <algorithm>
#include <cmath>
#include <vector>
#include <string>
#include <cstring>
#include <map>
#include <unordered_map>
#include <set>
#include <queue>
#include <iomanip>
#include <stack>
#include <cassert>
#include <iterator>
#include <bitset>
#include <fstream>
#define mod 998244353ll
#define LL long long
#define LD long double
#define MP make_pair
#define PB push_back
#define all(v) v.begin(),v.end()
using namespace std;

int n,d,dp[200005][452],upd[200005][452],sz[200005],ans=1,D;
vector<int> g[200005];
void dfs(int v)
{
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs(to);
	}

	dp[v][0]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		for(int k1=0;k1<=d && k1<=sz[v];k1++)
			for(int k2=0;k2<=d && k2<=sz[to];k2++)
				if(k1+k2+1>=d)
					upd[v][min(k2+1,k1)]=max(upd[v][min(k2+1,k1)],dp[to][k2]+dp[v][k1]);

		for(int k2=0;k2<=d && k2<=sz[to];k2++)
			upd[v][k2+1]=max(dp[to][k2],upd[v][k2+1]);

		sz[v]+=sz[to];
		for(int k=d;k>=0;k--)
		{
			dp[v][k]=max(dp[v][k],upd[v][k]);
			dp[v][k]=max(dp[v][k],dp[v][k+1]);
			upd[v][k]=0;
		}
	}


	for(int k=0;k<=d;k++)
		ans=max(ans,dp[v][k]);
}


void dfs2(int v)
{
	sz[v]=1;
	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		dfs2(to);
	}

	dp[v][1]=0;
	dp[v][0]=mod;

	for(int i=0;i<g[v].size();i++)
	{
		int to=g[v][i];
		for(int k1=0;k1<=D && k1<=sz[v];k1++)
			for(int k2=0;k2<=D && k2<=sz[to];k2++)
				if(dp[v][k1]+dp[to][k2]+1>=d)
					upd[v][k1+k2]=max(upd[v][k1+k2],min(dp[v][k1],dp[to][k2]+1));
		sz[v]+=sz[to];

		for(int k1=0;k1<=D && k1<=sz[v];k1++)
		{
			dp[v][k1]=max(dp[v][k1],upd[v][k1]);
			upd[v][k1]=-mod;
		}
	}
	
	// cout<<"!"<<v<<endl;
	// for(int k1=0;k1<=D && k1<=sz[v];k1++)
	// 	cout<<k1<<" = "<<dp[v][k1]<<endl;
	// cout<<endl;

	for(int k1=1;k1<=D && k1<=sz[v];k1++)
		if(dp[v][k1]>=0)
			ans=max(ans,k1);

}

int main()
{
	cin>>n>>d;
	for(int i=1;i<n;i++)
	{
		int p;
		scanf("%d",&p);
		g[p].PB(i);
	}
	D=(n-1)/d+1;
	if(n*D<=450 || 1)
	{
		for(int i=0;i<n;i++)
			for(int j=0;j<=D;j++)
				dp[i][j]=upd[i][j]=-mod;
		dfs2(0);
	}
	else
		dfs(0);

	cout<<ans<<endl;
	return 0;
}
 
/*

2 3
0 

4 3
0
0
0

*/

Compilation message

catinatree.cpp: In function 'void dfs(int)':
catinatree.cpp:31:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp:38:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp: In function 'void dfs2(int)':
catinatree.cpp:67:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp:76:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<g[v].size();i++)
              ~^~~~~~~~~~~~
catinatree.cpp: In function 'int main()':
catinatree.cpp:109:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&p);
   ~~~~~^~~~~~~~~

Subtask #1
0 / 11.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 40.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 49.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 6 ms 5112 KB Output isn't correct
2 Halted 0 ms 0 KB -