oj.uz

Submission #105371

# Submission time Handle Problem Language Result Execution time Memory
105371 2019-04-11T14:42:08 Z ryansee Chase (CEOI17_chase) C++14
100 / 100
 2811 ms 335888 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;
int n, A[MAXN];
ll dp[MAXN][102], V,ans, alu[MAXN][102];
vector<int>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]=-LLINF,alu[x][i]=0;
	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] = sum;  dp[x][0] = 0; if(V>=1)ans=max(ans,sum);}
	alu[x][1] = sum+A[p]; if(V>=1)ans = max(ans,sum+A[p]);
	priority_queue <ll> pq[102];
	for(auto i : v[x]) if(i!=p) {
		dfs(i,x); // sum -= A[i];
		FOR(b,0,V+1) {
			up(dp[x][b], dp[i][b]); pq[b].ph(max(dp[i][b],dp[i][b]));
			up(dp[x][b], max(dp[i][b],dp[i][b])); 
			if(b>0)up(dp[x][b],max(dp[i][b-1],dp[i][b-1])+sum);
			ans=max({ans,dp[x][b],dp[x][b]});
		}
		//~ sum += A[i];
	}
	// if(x==6) cerr << x << ' ' << dp[x][1][0] << '\n';
	//~ 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],alu[i][b]);
			up(alu[x][b],max(alu[i][b],alu[i][b]));
			if(b>0)up(alu[x][b],max(alu[i][b-1],alu[i][b-1])+sum);
			ans=max({ans,alu[x][b],alu[x][b]});
		}
		sum += A[i];
	}
	for(ll i = 1; i <= V; i++) dp[x][i]=max(dp[x][i],dp[x][i-1]), dp[x][i]=max(dp[x][i],dp[x][i-1]);
	for(ll i = 1; i <= V; i++) alu[x][i]=max(alu[x][i],alu[x][i-1]), alu[x][i]=max(alu[x][i],alu[x][i-1]);
	// if(x==6||x==7) cerr << x << ' ' << alu[x][1][0]
	FOR(b,0,V+1)pq[b].ph(-LLINF);
	for(auto i : v[x]) if(i!=p) { // will be my alu
		sum -= A[i];
		FOR(b,0,V+1) {
			bool zeroneed = 0, oneneed = 0; // ll hisdp = max({max(dp[i][b][0],dp[i][b][1])});
			if(pq[V-b].top() == max(dp[i][V-b],dp[i][V-b])) { pq[V-b].pop(); zeroneed = 1; }
			ll z0 = alu[i][b];
			ll o1 = max(alu[i][b],alu[i][b]);
			if(b>0)o1=max(o1,max(alu[i][b-1],alu[i][b-1])+sum+(b-1==0?A[i]:0ll));
			ans=max({ans,z0+pq[V-b].top(),o1+pq[V-b].top()});
			if(zeroneed) pq[V-b].ph(max(dp[i][V-b],dp[i][V-b]));
		}
		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)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 'void dfs(long long int, long long int)':
chase.cpp:74:23: warning: unused variable 'oneneed' [-Wunused-variable]
    bool zeroneed = 0, oneneed = 0; // ll hisdp = max({max(dp[i][b][0],dp[i][b][1])});
                       ^~~~~~~
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:92: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:92: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 2788 KB Output is correct
2 Correct 4 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 5 ms 2688 KB Output is correct
6 Correct 5 ms 2788 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2788 KB Output is correct
2 Correct 4 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 5 ms 2688 KB Output is correct
6 Correct 5 ms 2788 KB Output is correct
7 Correct 26 ms 6016 KB Output is correct
8 Correct 10 ms 6016 KB Output is correct
9 Correct 7 ms 4352 KB Output is correct
10 Correct 20 ms 4480 KB Output is correct
11 Correct 11 ms 4396 KB Output is correct
12 Correct 10 ms 4352 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1826 ms 332068 KB Output is correct
2 Correct 1566 ms 332248 KB Output is correct
3 Correct 2770 ms 253928 KB Output is correct
4 Correct 302 ms 166976 KB Output is correct
5 Correct 1655 ms 167372 KB Output is correct
6 Correct 1678 ms 167196 KB Output is correct
7 Correct 1459 ms 167292 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2788 KB Output is correct
2 Correct 4 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 5 ms 2688 KB Output is correct
6 Correct 5 ms 2788 KB Output is correct
7 Correct 26 ms 6016 KB Output is correct
8 Correct 10 ms 6016 KB Output is correct
9 Correct 7 ms 4352 KB Output is correct
10 Correct 20 ms 4480 KB Output is correct
11 Correct 11 ms 4396 KB Output is correct
12 Correct 10 ms 4352 KB Output is correct
13 Correct 1826 ms 332068 KB Output is correct
14 Correct 1566 ms 332248 KB Output is correct
15 Correct 2770 ms 253928 KB Output is correct
16 Correct 302 ms 166976 KB Output is correct
17 Correct 1655 ms 167372 KB Output is correct
18 Correct 1678 ms 167196 KB Output is correct
19 Correct 1459 ms 167292 KB Output is correct
20 Correct 1466 ms 167184 KB Output is correct
21 Correct 277 ms 168132 KB Output is correct
22 Correct 1485 ms 168568 KB Output is correct
23 Correct 285 ms 168284 KB Output is correct
24 Correct 1492 ms 168312 KB Output is correct
25 Correct 2811 ms 255008 KB Output is correct
26 Correct 1627 ms 335888 KB Output is correct
27 Correct 1814 ms 335760 KB Output is correct