oj.uz

Submission #121586

# Submission time Handle Problem Language Result Execution time Memory
121586 2019-06-26T19:47:12 Z sofhiasouza Chase (CEOI17_chase) C++14
70 / 100
 1568 ms 97192 KB 
#include <bits/stdc++.h>
#define pb push_back
using namespace std;
typedef long long int ll;

const int maxn = 1e5+10;

int n, v, vet[maxn];
ll dp[maxn][110];

vector < int > grafo[maxn];

ll dfs(int u, int val, int pai)
{
	if(val == 0) return 0;
	if(dp[u][val]) return dp[u][val];

	ll resp1 = 0, resp2 = 0, cont = 0;
	for(int i = 0 ; i < grafo[u].size() ; i++)
	{
		int v = grafo[u][i];
		if(v == pai) continue;

		cont += vet[v];
		resp1 = max(resp1, dfs(v, val-1, u));
		resp2 = max(resp2, dfs(v, val, u));
	}

	resp1 += cont;

	return dp[u][val] = max(resp1, resp2);
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n >> v;
	
	for(int i = 1 ; i <= n ; i++) cin >> vet[i];

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

	ll resp = dfs(1, v, 0);

	if(n <= 1000)
	{
		for(int i = 2 ; i <= n ; i++)
		{
			for(int j = 1 ; j <= n ; j++)
				for(int k = 0 ; k <= v ; k++) dp[j][k] = 0;
					
			resp = max(resp, dfs(i, v, 0));
		}
	}

	cout << resp << endl;
}

Compilation message

chase.cpp: In function 'll dfs(int, int, int)':
chase.cpp:19:20: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i = 0 ; i < grafo[u].size() ; i++)
                  ~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 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 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 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 1568 ms 3712 KB Output is correct
8 Correct 108 ms 3832 KB Output is correct
9 Correct 42 ms 3664 KB Output is correct
10 Correct 275 ms 3584 KB Output is correct
11 Correct 230 ms 3584 KB Output is correct
12 Correct 178 ms 3584 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 1494 ms 97192 KB Output is correct
2 Correct 1417 ms 97092 KB Output is correct
3 Correct 134 ms 92656 KB Output is correct
4 Correct 158 ms 92408 KB Output is correct
5 Correct 533 ms 92656 KB Output is correct
6 Correct 483 ms 92492 KB Output is correct
7 Correct 525 ms 92408 KB Output is correct

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2688 KB Output is correct
2 Correct 3 ms 2688 KB Output is correct
3 Correct 4 ms 2688 KB Output is correct
4 Correct 3 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 1568 ms 3712 KB Output is correct
8 Correct 108 ms 3832 KB Output is correct
9 Correct 42 ms 3664 KB Output is correct
10 Correct 275 ms 3584 KB Output is correct
11 Correct 230 ms 3584 KB Output is correct
12 Correct 178 ms 3584 KB Output is correct
13 Correct 1494 ms 97192 KB Output is correct
14 Correct 1417 ms 97092 KB Output is correct
15 Correct 134 ms 92656 KB Output is correct
16 Correct 158 ms 92408 KB Output is correct
17 Correct 533 ms 92656 KB Output is correct
18 Correct 483 ms 92492 KB Output is correct
19 Correct 525 ms 92408 KB Output is correct
20 Incorrect 236 ms 94456 KB Output isn't correct
21 Halted 0 ms 0 KB -