Submission #164405

#	Time	Username	Problem	Language	Result	Execution time	Memory
164405		Lawliet	Chase (CEOI17_chase)	C++14	30 / 100	262 ms	98424 KiB

chase

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXK = 110;
const int MAXN = 100010;

int n, k;

int v[MAXN];

lli dp[MAXN][MAXK];

vector< int > adj[MAXN];

void DFS(int cur, int p)
{
	lli sum = 0;

	for(int i = 0 ; i < adj[cur].size() ; i++)
	{
		int viz = adj[cur][ i ];

		if( viz == p ) continue;

		sum += v[ viz ];
		DFS( viz , cur );
	}

	for(int j = 1 ; j <= k ; j++)
	{
		lli maxDP0 = 0;
		lli maxDP1 = 0;

		for(int i = 0 ; i < adj[cur].size() ; i++)
		{
			int viz = adj[cur][ i ];

			if( viz == p ) continue;

			maxDP0 = max( maxDP0 , dp[viz][ j ] );
			maxDP1 = max( maxDP1 , dp[viz][ j - 1 ] );
		}

		dp[ cur ][ j ] = max( maxDP1 + sum , maxDP0 );
	}
}

int main()
{
	scanf("%d %d",&n,&k);

	for(int i = 1 ; i <= n ; i++)
		scanf("%d",&v[i]);

	for(int i = 1 ; i < n ; i++)
	{
		int U, V;
		scanf("%d %d",&U,&V);

		adj[ U ].push_back( V );
		adj[ V ].push_back( U );
	}

	DFS( 1 , 0 );

	printf("%lld\n",dp[1][k]);
}

Compilation message (stderr)

chase.cpp: In function 'void DFS(int, int)':
chase.cpp:21:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
chase.cpp:36:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
chase.cpp: In function 'int main()':
chase.cpp:52:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&k);
  ~~~~~^~~~~~~~~~~~~~~
chase.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
chase.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d",&U,&V);
   ~~~~~^~~~~~~~~~~~~~~

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 30 / 30
• Subtask 4: 0 / 30