oj.uz

Submission #161895

# Submission time Handle Problem Language Result Execution time Memory
161895 2019-11-05T08:32:45 Z amoo_safar Chase (CEOI17_chase) C++14
100 / 100
 582 ms 170896 KB 
#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
 
#define pb push_back
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define debug(x) cerr << #x << " : " << x << '\n'
 
using namespace std;
using namespace __gnu_pbds;
 
typedef long long ll;
typedef long double ld;
typedef string str;
typedef pair<ll, ll> pll;
typedef tree<ll, null_type, less<ll>, rb_tree_tag, tree_order_statistics_node_update> ordered_set;
 
const ll Mod = 998244353;
const ll Inf = 2242545357980376863LL;
const ll Log = 20;
const ll N = 1ll << Log;
const int Maxn = 1e5 + 10;
const int Maxk = 101;
const int Base = 101;
 
ll dp1[Maxn][Maxk], dp2[Maxn][Maxk], p[Maxn];
vector<ll> G[Maxn];
 
vector<ll> S;
ll V, ans = 0;
 
ll mx[Maxk];
 
void DFS(ll u, ll pa){
	//debug(u);
	ll sm = 0;
	for(auto adj : G[u]){
		sm += p[adj];
		if(adj != pa) DFS(adj, u);
	}
	//cerr << u << " " << sm << '\n';
	ll sm2 = sm - (pa != -1 ? p[pa] : 0);
	S.clear();
	for(auto adj : G[u]){
		if(adj != pa) S.pb(adj);
		dp1[u][1] = max(sm, dp1[u][1]);
		for(int i = 1; i <= V; i++){
			dp1[u][i] = max({dp1[u][i], dp1[adj][i], dp1[adj][i - 1] + sm - p[adj] });
			dp2[u][i] = max({dp2[u][i], dp2[adj][i], dp2[adj][i - 1] + sm2 });
			ans = max({ans, dp1[u][i], dp2[u][i], dp2[adj][i - 1] + sm});
		}
	}
	
	if(S.size() < 2) return ;
	for(auto adj : S){
		for(int i = 1; i <= V; i++) dp1[adj][i] = max(dp1[adj][i], dp1[adj][i - 1]);
		for(int i = 1; i <= V; i++) dp2[adj][i] = max(dp2[adj][i], dp2[adj][i - 1]);
	}
	
	memset(mx, 0, sizeof mx);
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		
		for(int i = 0; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i - 1] + sm - p[adj]);
	}
	reverse(all(S));
	memset(mx, 0, sizeof mx);
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		
		for(int i = 0; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], dp1[adj][i - 1] + sm - p[adj]);
	}
}
 
int main(){
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll n;
	cin >> n >> V;
	for(int i = 1; i <= n; i++) cin >> p[i];
	ll u, v;
	for(int i = 1; i < n; i++){
		cin >> u >> v;
		G[u].pb(v);
		G[v].pb(u);
	}
	DFS(1, -1);
	cout << ans << '\n';
	return 0;
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 4472 KB Output is correct
8 Correct 7 ms 4344 KB Output is correct
9 Correct 7 ms 4344 KB Output is correct
10 Correct 8 ms 4344 KB Output is correct
11 Correct 7 ms 4344 KB Output is correct
12 Correct 7 ms 4348 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 498 ms 170804 KB Output is correct
2 Correct 493 ms 170896 KB Output is correct
3 Correct 478 ms 167060 KB Output is correct
4 Correct 307 ms 165528 KB Output is correct
5 Correct 511 ms 165368 KB Output is correct
6 Correct 522 ms 165468 KB Output is correct
7 Correct 517 ms 165372 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 4 ms 2680 KB Output is correct
4 Correct 4 ms 2680 KB Output is correct
5 Correct 4 ms 2680 KB Output is correct
6 Correct 4 ms 2680 KB Output is correct
7 Correct 9 ms 4472 KB Output is correct
8 Correct 7 ms 4344 KB Output is correct
9 Correct 7 ms 4344 KB Output is correct
10 Correct 8 ms 4344 KB Output is correct
11 Correct 7 ms 4344 KB Output is correct
12 Correct 7 ms 4348 KB Output is correct
13 Correct 498 ms 170804 KB Output is correct
14 Correct 493 ms 170896 KB Output is correct
15 Correct 478 ms 167060 KB Output is correct
16 Correct 307 ms 165528 KB Output is correct
17 Correct 511 ms 165368 KB Output is correct
18 Correct 522 ms 165468 KB Output is correct
19 Correct 517 ms 165372 KB Output is correct
20 Correct 532 ms 165524 KB Output is correct
21 Correct 210 ms 86556 KB Output is correct
22 Correct 518 ms 165420 KB Output is correct
23 Correct 406 ms 165468 KB Output is correct
24 Correct 508 ms 165400 KB Output is correct
25 Correct 471 ms 167180 KB Output is correct
26 Correct 582 ms 170824 KB Output is correct
27 Correct 521 ms 170872 KB Output is correct