oj.uz

Submission #58015

# Submission time Handle Problem Language Result Execution time Memory
58015 2018-07-16T15:45:15 Z thiago4532 Chase (CEOI17_chase) C++17
0 / 100
 3597 ms 98036 KB 
#include <bits/stdc++.h>

using namespace std;
const int maxn = 1e5 + 10, maxv = 110;
int dp[maxn][maxv][2], 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 solve(int u, int j, bool usa){
	if(j < 0 || (j == 0 && !usa)) return 0;
	if(dp[u][j][usa] != -1) return dp[u][j][usa];

	int ans = (usa ? gain[u] : 0);
	for(auto v : grafo[u]){
		if(pai[u] == v) continue;
		ans = max(ans, max(solve(v, j, 0), solve(v, j-1, 1)) + (usa ? gain[u] : 0));
	}
	return dp[u][j][usa] = ans;
}

int main(){
	ios::sync_with_stdio(false), cin.tie(0);
	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);
	}

	int resp=0;
	for(int u=1;u<=n;u++){
		if(u > 1 && n > 1010) break;
		memset(dp, -1, sizeof dp);
		memset(pai, 0, sizeof pai);
		memset(gain, 0, sizeof gain);
		dfs(u);

		resp = max(resp, solve(u, 1, 0));
		for(int j=1;j<=v;j++) resp = max(resp, max(solve(u, j, 0), solve(u, j-1, 1)));
	}
	cout << resp << "\n";
	return 0;
}

Subtask #1
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 89592 KB Output is correct
2 Correct 239 ms 89828 KB Output is correct
3 Incorrect 244 ms 89828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 89592 KB Output is correct
2 Correct 239 ms 89828 KB Output is correct
3 Incorrect 244 ms 89828 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 249 ms 89592 KB Output is correct
2 Correct 239 ms 89828 KB Output is correct
3 Incorrect 244 ms 89828 KB Output isn't correct
4 Halted 0 ms 0 KB -