oj.uz

Submission #161888

# Submission time Handle Problem Language Result Execution time Memory
161888 2019-11-05T07:44:01 Z amoo_safar Chase (CEOI17_chase) C++14
50 / 100
 555 ms 174712 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 = 103;
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();
	dp1[u][1] = sm;
	for(auto adj : G[u]){
		if(adj != pa) S.pb(adj);
	}
	for(auto adj : S){
		dp1[u][1] = sm;
		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);
	mx[1] = sm;
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		ans = max(ans, mx[V]);
		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]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], mx[i - 1]);
	}
	reverse(all(S));
	memset(mx, 0, sizeof mx);
	mx[1] = sm;
	for(auto adj : S){
		for(int i = 0; i <= V; i++) ans = max(ans, mx[V - i] + dp2[adj][i]);
		ans = max(ans, mx[V]);
		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]);
		for(int i = 1; i <= V; i++) mx[i] = max(mx[i], mx[i - 1]);
	}
}

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;
}
/*
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

*/

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 2808 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct

Subtask #2
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 2808 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 4476 KB Output is correct
8 Incorrect 7 ms 4472 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 555 ms 174680 KB Output is correct
2 Correct 549 ms 174712 KB Output is correct
3 Correct 468 ms 169584 KB Output is correct
4 Correct 274 ms 168568 KB Output is correct
5 Correct 551 ms 168572 KB Output is correct
6 Correct 543 ms 168568 KB Output is correct
7 Correct 552 ms 168668 KB Output is correct

Subtask #4
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 2808 KB Output is correct
5 Correct 5 ms 2728 KB Output is correct
6 Correct 4 ms 2780 KB Output is correct
7 Correct 9 ms 4476 KB Output is correct
8 Incorrect 7 ms 4472 KB Output isn't correct
9 Halted 0 ms 0 KB -