oj.uz

Submission #105336

# Submission time Handle Problem Language Result Execution time Memory
105336 2019-04-11T11:43:42 Z ryansee Chase (CEOI17_chase) C++14
70 / 100
 1587 ms 492060 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, alu[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]=alu[x][i][0]=alu[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) { alu[x][1][1] = dp[x][1][1] = sum; alu[x][1][1] += A[p]; alu[x][0][1] = dp[x][0][1] = 0; if(V>=1)ans=max(ans,sum+A[p]);}
	
	
	for(auto i : v[x]) if(i!=p) {
		dfs(i,x); // sum -= A[i];
		FOR(b,0,V+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][1]});
		}
		//~ sum += A[i];
	}
	//~ 0 - went down
	//~ 1 - stayed
	if(p!=-1)sum += A[p];
	for(auto i : v[x]) if(i!=p) {
		sum -= A[i];
		FOR(b,0,V+1) {
			// up(alu[x][b][0],alu[i][b][1]);
			up(alu[x][b][1],max(alu[i][b][0],alu[i][b][1]));
			if(b>0)up(alu[x][b][1],max(alu[i][b-1][0],alu[i][b-1][1])+sum);
			ans=max({ans,alu[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:72: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:72: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 4 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 1587 ms 7636 KB Output is correct
8 Correct 153 ms 7672 KB Output is correct
9 Correct 132 ms 7588 KB Output is correct
10 Correct 1419 ms 7672 KB Output is correct
11 Correct 644 ms 7552 KB Output is correct
12 Correct 194 ms 7552 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 799 ms 491932 KB Output is correct
2 Correct 801 ms 492060 KB Output is correct
3 Correct 577 ms 487020 KB Output is correct
4 Correct 455 ms 486560 KB Output is correct
5 Correct 778 ms 486648 KB Output is correct
6 Correct 821 ms 486776 KB Output is correct
7 Correct 786 ms 486648 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2816 KB Output is correct
2 Correct 5 ms 2816 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 5 ms 2688 KB Output is correct
7 Correct 1587 ms 7636 KB Output is correct
8 Correct 153 ms 7672 KB Output is correct
9 Correct 132 ms 7588 KB Output is correct
10 Correct 1419 ms 7672 KB Output is correct
11 Correct 644 ms 7552 KB Output is correct
12 Correct 194 ms 7552 KB Output is correct
13 Correct 799 ms 491932 KB Output is correct
14 Correct 801 ms 492060 KB Output is correct
15 Correct 577 ms 487020 KB Output is correct
16 Correct 455 ms 486560 KB Output is correct
17 Correct 778 ms 486648 KB Output is correct
18 Correct 821 ms 486776 KB Output is correct
19 Correct 786 ms 486648 KB Output is correct
20 Incorrect 874 ms 486636 KB Output isn't correct
21 Halted 0 ms 0 KB -