oj.uz

Submission #105277

# Submission time Handle Problem Language Result Execution time Memory
105277 2019-04-11T06:00:50 Z ryansee Chase (CEOI17_chase) C++14
70 / 100
 1634 ms 493304 KB 
#include "bits/stdc++.h"
using namespace std;
#define FAST ios::sync_with_stdio(false); cin.tie(0);
#define ll long long int
#define ld long double
#define pb push_back
#define ins insert
#define ph push
#define mmst(x,v) memset(x,v,sizeof(x))
#define all(x) (x).begin(), (x).end()
#define FOR(i,s,e) for(ll i=s;i<e;i++)
#define cbr cerr << "hi\n"
#define MAXN (100006)
#define LLINF ((long long)1e18)
typedef pair <ll, ll> pi;
typedef pair <ll, pi> spi;
ll n, A[MAXN], dp[MAXN][102][3], V,ans, down[MAXN][102][3];
vector<ll>v[MAXN];
// 0 - went down (aka. kid pressed) 
// 1 - ready to go up (aka. pressed)
void up(ll &x, ll y) { x=max(x,y); }
void dfs(ll x, ll p) {
    FOR(i,0,V+1) dp[x][i][0]=dp[x][i][1]=down[x][i][0]=down[x][i][1]=-LLINF;
	ll sum = 0; for(auto i:v[x])if(i!=p)sum+=A[i];
	//~ if(p == -1) {
		//~ dp[x][1][1] = sum; if(V>=1)ans = max(ans,sum);
		//~ dp[x][0][1] = 0;
	//~ } else {
		//~ FOR(i,0,V+1) {
			//~ up(dp[x][i][0],dp[p][i][1]);
			//~ up(dp[x][i][1],dp[p][i][0]); // np
			//~ up(dp[x][i][1],dp[p][i][1]);
			//~ if(i>0)up(dp[x][i][1],dp[p][i-1][0]+sum); // press
			//~ if(i>0)up(dp[x][i][1],dp[p][i-1][1]+sum);
//~ // 			up(dp[x][i][2],max({dp[p][i][2],dp[p][i][0]}));
			//~ ans=max({ans,dp[x][i][0],dp[x][i][1]});
		//~ }
	//~ }
	if(v[x].size()==1&&p!=-1) { dp[x][1][1] = sum; dp[x][0][1] = 0; ans=max(ans,sum);}
	
	
	for(auto i : v[x]) if(i!=p) {
		dfs(i,x); // sum -= A[i];
		FOR(b,0,V+1) {
			up(dp[x][b][0], dp[i][b][1]);
			up(dp[x][b][1], max(dp[i][b][0],dp[i][b][1]));
			if(b>0)up(dp[x][b][1],max(dp[i][b-1][0],dp[i][b-1][1])+sum);
			ans=max({ans,dp[x][b][0],dp[x][b][1]});
		}
		//~ sum += A[i];
	}
	
	return;
}

int main()
{
	// freopen("in","r",stdin);
	FAST
	cin>>n>>V; if(n==1) { cout << 0 << '\n'; return 0; }
	FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
// 	ll ans = 0;
	FOR(i,1,n+1) {
	    if((i>1&&n>1000))break;
// 		for(ll i=0;i<MAXN;i++) for(ll j=0;j<102;j++) dp[i][j][0]=dp[i][j][1]=dp[i][j][2]=-LLINF;
		dfs(i,-1);
	// ll ans = 0;
// 		for(ll i=1;i<=n;i++) for(ll j=0;j<=V;j++)ans=max({ans,dp[i][j][0],dp[i][j][1],dp[i][j][2]}); 
	}
	//~ dfs(6,-1);
	cout<<ans<<'\n';
}
/*
 * 
12 2
2 3 3 8 1 5 6 7 8 3 5 4
2 1
2 7
3 4
4 7
7 6
5 6
6 8
6 9
7 10
10 11
10 12
* 
*/

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:11:20: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
 #define FOR(i,s,e) for(ll i=s;i<e;i++)
                    ^
chase.cpp:61:2: note: in expansion of macro 'FOR'
  FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
  ^~~
chase.cpp:61:25: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  FOR(i,1,n+1)cin>>A[i]; for(ll i=0;i<n-1;i++) { ll a, b; cin >> a >> b; v[a].pb(b); v[b].pb(a); }
                         ^~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 1305 ms 7628 KB Output is correct
8 Correct 134 ms 7552 KB Output is correct
9 Correct 123 ms 7552 KB Output is correct
10 Correct 1634 ms 7604 KB Output is correct
11 Correct 686 ms 7672 KB Output is correct
12 Correct 177 ms 7672 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 853 ms 493232 KB Output is correct
2 Correct 770 ms 493304 KB Output is correct
3 Correct 553 ms 488628 KB Output is correct
4 Correct 572 ms 488440 KB Output is correct
5 Correct 940 ms 488528 KB Output is correct
6 Correct 905 ms 488332 KB Output is correct
7 Correct 943 ms 488440 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 2688 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2816 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2816 KB Output is correct
7 Correct 1305 ms 7628 KB Output is correct
8 Correct 134 ms 7552 KB Output is correct
9 Correct 123 ms 7552 KB Output is correct
10 Correct 1634 ms 7604 KB Output is correct
11 Correct 686 ms 7672 KB Output is correct
12 Correct 177 ms 7672 KB Output is correct
13 Correct 853 ms 493232 KB Output is correct
14 Correct 770 ms 493304 KB Output is correct
15 Correct 553 ms 488628 KB Output is correct
16 Correct 572 ms 488440 KB Output is correct
17 Correct 940 ms 488528 KB Output is correct
18 Correct 905 ms 488332 KB Output is correct
19 Correct 943 ms 488440 KB Output is correct
20 Incorrect 957 ms 488428 KB Output isn't correct
21 Halted 0 ms 0 KB -