oj.uz

Submission #58016

# Submission time Handle Problem Language Result Execution time Memory
58016 2018-07-16T15:46:46 Z thiago4532 Chase (CEOI17_chase) C++17
50 / 100
 4000 ms 193864 KB 
#include <bits/stdc++.h>
#define int long long

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

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));
		resp = max(resp, max(solve(u, v, 0), solve(u, v-1, 1)));
	}
	cout << resp << "\n";
	return 0;
}

Compilation message

chase.cpp:30:6: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
 main(){
      ^

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 176516 KB Output is correct
2 Correct 532 ms 176612 KB Output is correct
3 Correct 489 ms 176668 KB Output is correct
4 Correct 547 ms 176680 KB Output is correct
5 Correct 576 ms 176748 KB Output is correct
6 Correct 495 ms 176748 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 176516 KB Output is correct
2 Correct 532 ms 176612 KB Output is correct
3 Correct 489 ms 176668 KB Output is correct
4 Correct 547 ms 176680 KB Output is correct
5 Correct 576 ms 176748 KB Output is correct
6 Correct 495 ms 176748 KB Output is correct
7 Execution timed out 4027 ms 176856 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3797 ms 185988 KB Output is correct
2 Correct 3264 ms 188068 KB Output is correct
3 Correct 223 ms 188068 KB Output is correct
4 Correct 270 ms 188068 KB Output is correct
5 Correct 1438 ms 189708 KB Output is correct
6 Correct 1159 ms 191828 KB Output is correct
7 Correct 1346 ms 193864 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 520 ms 176516 KB Output is correct
2 Correct 532 ms 176612 KB Output is correct
3 Correct 489 ms 176668 KB Output is correct
4 Correct 547 ms 176680 KB Output is correct
5 Correct 576 ms 176748 KB Output is correct
6 Correct 495 ms 176748 KB Output is correct
7 Execution timed out 4027 ms 176856 KB Time limit exceeded
8 Halted 0 ms 0 KB -