oj.uz

Submission #59673

# Submission time Handle Problem Language Result Execution time Memory
59673 2018-07-22T21:48:10 Z thiago4532 Chase (CEOI17_chase) C++17
0 / 100
 4000 ms 56000 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxk = 1e2 + 10;
vector<int> grafo[maxn];
int n, k;
int gain[maxn], x[maxn], dp[maxn][maxk];

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

		dfs(v, u);
	}
}

void solve(int u, int p=0){
	for(int l=0;l<=k;l++)
		dp[u][l] = 0;

	for(auto v : grafo[u]){
		if(v == p) continue;
		solve(v, u);

		for(int l=1;l<=k;l++)
			dp[u][l] = max({dp[u][l], dp[v][l], dp[v][l-1] + gain[u]});
	}
}

int main(){
	//ios::sync_with_stdio(false), cin.tie(0);
	cin >> n >> k;
	for(int i=1;i<=n;i++)
		cin >> x[i];

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

	int ans=0;
	for(int i=1;i<=n;i++){
		dfs(i);
		solve(i);
		// cout << "gain: " << gain[i] << "\n";
		// cout << "dp: " << dp[i][k] << "\n";
		ans = max(ans, dp[i][k]);
	}
	cout << ans << "\n";
	
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Incorrect 5 ms 2852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Incorrect 5 ms 2852 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4021 ms 56000 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 5 ms 2680 KB Output is correct
3 Incorrect 5 ms 2852 KB Output isn't correct
4 Halted 0 ms 0 KB -