oj.uz

Submission #57976

# Submission time Handle Problem Language Result Execution time Memory
57976 2018-07-16T15:00:08 Z thiago4532 Chase (CEOI17_chase) C++17
0 / 100
 3810 ms 96996 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxv = 110;
int dp[2][maxn][maxv], p[maxn], n, v, pai[maxn], gain[maxn];
vector<int> grafo[maxn];

void dfs(int u){
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		pai[v] = u;
		gain[u] += p[v];
		dfs(v);
	}
}

int solve1(int u, int j){
	if(j == 0) return 0;
	if(dp[0][u][j] != -1) return dp[0][u][j];

	int ans=-0x3f3f3f3f;
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		int resp = max(solve1(v, j), solve1(v, j-1) + gain[v] - p[u]);

		ans = max(ans, resp);
	}
	return dp[0][u][j] = ans;
}

int solve2(int u, int j){
	if(j == 0) return 0;
	if(dp[1][u][j] != -1) return dp[1][u][j];

	int ans=-0x3f3f3f3f;
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		int resp = max(solve2(v, j), solve2(v, j-1) + gain[u] - p[v]);

		ans = max(ans, resp);
	}
	return dp[1][u][j] = ans;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	memset(dp, -1, sizeof dp);
	cin >> n >> v;
	for(int i=1;i<=n;i++)
		cin >> p[i];

	for(int i=1;i<n;i++){
		int a, b;
		cin >> a >> b;
		grafo[a].push_back(b);
		grafo[b].push_back(a);
	}
	dfs(1);
	solve1(1, v);
	solve2(1, v);

	int resp = 0;
	for(int i=1;i<=n;i++){
		for(int j=1;j<=v;j++){
			for(auto u : grafo[i]){
				resp = max(resp, dp[1][i][j] + dp[0][u][v-j]);
			}
		}
	}

	cout << resp << "\n";
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 88828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 88828 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 3810 ms 96996 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Incorrect 69 ms 88828 KB Output isn't correct
2 Halted 0 ms 0 KB -