oj.uz

Submission #164408

# Submission time Handle Problem Language Result Execution time Memory
164408 2019-11-20T13:07:06 Z Lawliet Chase (CEOI17_chase) C++14
30 / 100
 354 ms 143676 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];
int maxDP[MAXN][MAXK][2];

lli ans;

lli sum[MAXN];
lli dp[MAXN][MAXK];

vector< int > adj[MAXN];

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

		if( viz == p ) continue;

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

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

			if( viz == p ) continue;

			if( dp[viz][j] > dp[ maxDP[cur][j][1] ][ j ] ) maxDP[ cur ][ j ][1] = viz;
			if( dp[ maxDP[cur][j][1] ][ j ] > dp[ maxDP[cur][j][0] ][ j ]) 
				swap( maxDP[ cur ][ j ][0] , maxDP[ cur ][ j ][1] );
		}

		dp[ cur ][ j ] = dp[ maxDP[cur][j - 1][0] ][ j - 1 ] + sum[ cur ];
		dp[ cur ][ j ] = max( dp[ cur ][ j ] , dp[ maxDP[cur][j][0] ][ j ] );
	}
}

void DFSRotate(int cur, int p)
{
	ans = max( ans , dp[cur][k] );

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

		if( viz == p ) continue;

		lli oldSumCur = sum[ cur ];
		lli oldSumViz = sum[ viz ];

		sum[ cur ] -= v[ viz ];
		sum[ viz ] += v[ cur ];

		DFSRotate( viz , cur );

		sum[ cur ] = oldSumCur;
		sum[ viz ] = oldSumViz;
	}
}

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 );
	}

	DFSCalculate( 1 , 0 );
	//DFSRotate( 1 , 0 );

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

Compilation message

chase.cpp: In function 'void DFSCalculate(int, int)':
chase.cpp:23:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < adj[cur].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~
chase.cpp:35:21: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(int i = 0 ; i < adj[cur].size() ; i++)
                   ~~^~~~~~~~~~~~~~~~~
chase.cpp: In function 'void DFSRotate(int, int)':
chase.cpp:55:20: 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:76: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:79:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d",&v[i]);
   ~~~~~^~~~~~~~~~~~
chase.cpp:84: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 2680 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 2680 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 299 ms 140024 KB Output is correct
2 Correct 302 ms 139868 KB Output is correct
3 Correct 324 ms 92956 KB Output is correct
4 Correct 238 ms 140924 KB Output is correct
5 Correct 348 ms 143676 KB Output is correct
6 Correct 354 ms 143404 KB Output is correct
7 Correct 348 ms 143372 KB Output is correct

Subtask #4
0 / 30.0

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