oj.uz

Submission #483039

# Submission time Handle Problem Language Result Execution time Memory
483039 2021-10-27T14:18:27 Z ntabc05101 Chase (CEOI17_chase) C++14
100 / 100
 379 ms 254804 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 dfs(int u, int f = 0)
{
	for(int v: graph[u])
	{	
		if(v == f) continue;
		dfs(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];
		}
	}
 
	dfs(1);
	rotate(1);
 
	cout << ans << '\n';
}

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2688 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4812 KB Output is correct
9 Correct 3 ms 4428 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 329 ms 228988 KB Output is correct
2 Correct 342 ms 230880 KB Output is correct
3 Correct 231 ms 182092 KB Output is correct
4 Correct 231 ms 252424 KB Output is correct
5 Correct 366 ms 254728 KB Output is correct
6 Correct 374 ms 254532 KB Output is correct
7 Correct 366 ms 254504 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2636 KB Output is correct
2 Correct 1 ms 2636 KB Output is correct
3 Correct 1 ms 2636 KB Output is correct
4 Correct 1 ms 2688 KB Output is correct
5 Correct 1 ms 2636 KB Output is correct
6 Correct 2 ms 2636 KB Output is correct
7 Correct 4 ms 4940 KB Output is correct
8 Correct 4 ms 4812 KB Output is correct
9 Correct 3 ms 4428 KB Output is correct
10 Correct 4 ms 5196 KB Output is correct
11 Correct 4 ms 5196 KB Output is correct
12 Correct 4 ms 5068 KB Output is correct
13 Correct 329 ms 228988 KB Output is correct
14 Correct 342 ms 230880 KB Output is correct
15 Correct 231 ms 182092 KB Output is correct
16 Correct 231 ms 252424 KB Output is correct
17 Correct 366 ms 254728 KB Output is correct
18 Correct 374 ms 254532 KB Output is correct
19 Correct 366 ms 254504 KB Output is correct
20 Correct 378 ms 254748 KB Output is correct
21 Correct 102 ms 9408 KB Output is correct
22 Correct 368 ms 254804 KB Output is correct
23 Correct 232 ms 252228 KB Output is correct
24 Correct 379 ms 254792 KB Output is correct
25 Correct 209 ms 181656 KB Output is correct
26 Correct 305 ms 231008 KB Output is correct
27 Correct 319 ms 231020 KB Output is correct