# | Submission time | Handle | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
164407 | 2019-11-20T13:05:06 Z | Lawliet | Chase (CEOI17_chase) | C++14 | 418 ms | 183016 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 = 0 ; j <= k ; j++) maxDP[ cur ][ j ][ 0 ] = maxDP[ cur ][ j ][ 1 ] = 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
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Correct | 383 ms | 183016 KB | Output is correct |
2 | Correct | 387 ms | 182852 KB | Output is correct |
3 | Incorrect | 418 ms | 178988 KB | Output isn't correct |
4 | Halted | 0 ms | 0 KB | - |
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
1 | Incorrect | 4 ms | 2680 KB | Output isn't correct |
2 | Halted | 0 ms | 0 KB | - |