oj.uz

Submission #164405

# Submission time Handle Problem Language Result Execution time Memory
164405 2019-11-20T12:52:20 Z Lawliet Chase (CEOI17_chase) C++14
30 / 100
 262 ms 98424 KB 
#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

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.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 210 ms 98424 KB Output is correct
2 Correct 208 ms 98268 KB Output is correct
3 Correct 262 ms 94832 KB Output is correct
4 Correct 159 ms 94456 KB Output is correct
5 Correct 216 ms 94536 KB Output is correct
6 Correct 221 ms 94732 KB Output is correct
7 Correct 212 ms 94584 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 4 ms 2808 KB Output isn't correct
2 Halted 0 ms 0 KB -