oj.uz

Submission #122224

# Submission time Handle Problem Language Result Execution time Memory
122224 2019-06-27T21:26:28 Z sams Chase (CEOI17_chase) C++14
100 / 100
 808 ms 252920 KB 
#include <bits/stdc++.h>
 
using namespace std;
 
typedef long long ll;
const int maxn = 1e5+10, maxk = 110;
 
int n, k;
ll dp[maxn][maxk], dp2[maxn][maxk], ant[maxn][maxk], ans, vis[maxn], vet[maxn];
 
vector <int> graph[maxn];
 
void solve(int u, int f = 0)
{
	for(int v: graph[u])
	{	
		if(v == f) continue;
		
		solve(v, u);
 
		for(int i = 1 ; i <= k ; ++i)
		{
			ll val = max(dp[v][i-1] + vis[v] - vet[u], dp[v][i]);
		
			if(val > dp[u][i]) dp2[u][i] = dp[u][i], dp[u][i] = val;
			else if(val > dp2[u][i]) dp2[u][i] = val;
		}
	}
}
 
void rotate(int u, int f = 0)
{
	for(int i = 1 ; i <= k ; ++i)
	{
		ans = max({ans, dp[u][i], dp[u][i-1] + vis[u]});
	}
 
	for(int v: graph[u])
	{
		if(v == f) continue;
 
		for(int i = 1 ; i <= k ; ++i)
		{
			ant[u][i] = dp[u][i];
			
			ll val = max(dp[v][i], dp[v][i-1] + vis[v] - vet[u]);
 
			if(val == dp[u][i])
			{
				dp[u][i] = dp2[u][i];
			}
		}
 
		for(int i = 1 ; i <= k ; ++i)
		{
			ll val = max(dp[u][i], dp[u][i-1] + vis[u] - vet[v]);
 
			if(val > dp[v][i]) dp2[v][i] = dp[v][i], dp[v][i] = val;
			else if(val > dp2[v][i]) dp2[v][i] = val;
		}
 
		rotate(v, u);
 
		for(int i = 1 ; i <= k ; ++i) dp[u][i] = ant[u][i];
	}
}
 
int main()
{
	cin >> n >> k;
 
	for(int i = 1 ; i <= n ; ++i) cin >> vet[i];
 
	for(int i = 1 ; i < n ; ++i)
	{
		int u, v;
		cin >> u >> v;
 
		graph[u].push_back(v);
		graph[v].push_back(u);
	}
 
	for(int i = 1 ; i <= n ; ++i)
	{
		for(int v: graph[i])
		{
			vis[i] += vet[v];
		}
	}

	solve(1);

	rotate(1);
 
	cout << ans << '\n';
}

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 6 ms 4480 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 566 ms 228100 KB Output is correct
2 Correct 808 ms 228272 KB Output is correct
3 Correct 329 ms 179952 KB Output is correct
4 Correct 376 ms 250376 KB Output is correct
5 Correct 715 ms 252920 KB Output is correct
6 Correct 728 ms 252876 KB Output is correct
7 Correct 709 ms 252632 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 4 ms 2688 KB Output is correct
3 Correct 3 ms 2688 KB Output is correct
4 Correct 4 ms 2688 KB Output is correct
5 Correct 4 ms 2688 KB Output is correct
6 Correct 4 ms 2688 KB Output is correct
7 Correct 7 ms 4992 KB Output is correct
8 Correct 6 ms 4992 KB Output is correct
9 Correct 6 ms 4480 KB Output is correct
10 Correct 8 ms 5248 KB Output is correct
11 Correct 7 ms 5120 KB Output is correct
12 Correct 7 ms 5120 KB Output is correct
13 Correct 566 ms 228100 KB Output is correct
14 Correct 808 ms 228272 KB Output is correct
15 Correct 329 ms 179952 KB Output is correct
16 Correct 376 ms 250376 KB Output is correct
17 Correct 715 ms 252920 KB Output is correct
18 Correct 728 ms 252876 KB Output is correct
19 Correct 709 ms 252632 KB Output is correct
20 Correct 750 ms 252748 KB Output is correct
21 Correct 131 ms 7544 KB Output is correct
22 Correct 715 ms 252600 KB Output is correct
23 Correct 378 ms 250484 KB Output is correct
24 Correct 710 ms 252920 KB Output is correct
25 Correct 316 ms 179996 KB Output is correct
26 Correct 531 ms 228228 KB Output is correct
27 Correct 558 ms 228344 KB Output is correct