oj.uz

Submission #310431

# Submission time Handle Problem Language Result Execution time Memory
310431 2020-10-06T22:46:36 Z pedroslrey Chase (CEOI17_chase) C++14
40 / 100
 4000 ms 98808 KB 
#include <bits/stdc++.h>

using namespace std;
using lli = long long int;

const int MAXN = 100010;
const int MAXM = 110;
 
#define debug(args...) //fprintf(stderr, args);

int n, m;
lli ps[MAXN];
lli dp[MAXN][MAXM];
vector<int> graph[MAXN];
 
void dfs(int v, int p) {
	lli sum = 0;
 
	for (int u: graph[v]) {
		if (u == p) continue;
 
		sum +=ps[u];
		dfs(u, v);
	}
 
	for (int k = 0; k <= m; k++) {
		dp[v][k] = 0;
		for (int u: graph[v]) {
			if (u == p)	continue;
 
			dp[v][k] = max(dp[v][k], dp[u][k]);
			if (k)	dp[v][k] = max(dp[v][k], dp[u][k - 1] + sum);
		}
	}

	debug("dp[%d][%d] = %d\n", v, m, dp[v][m]);
}
 
int main() {
	scanf("%d %d", &n, &m);
 
	for (int i = 1; i <= n; ++i)
		scanf("%lld", &ps[i]);
 
	for (int i = 0; i < n-1; ++i) {
		int u, v;
		scanf("%d %d", &u, &v);
		graph[u].push_back(v);
		graph[v].push_back(u);
	}	
 
	lli ans = 0;

	for (int i = 1; i <= n; ++i) {
		dfs(i, i);
		debug("OI\n");

		for (int j = 1; j <= n; ++j)
			ans = max(ans, dp[j][m]);
	}
	printf("%lld\n", ans);
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:40:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   40 |  scanf("%d %d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~~
chase.cpp:43:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   43 |   scanf("%lld", &ps[i]);
      |   ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:47:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   47 |   scanf("%d %d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 480 ms 3704 KB Output is correct
8 Correct 48 ms 3584 KB Output is correct
9 Correct 52 ms 3584 KB Output is correct
10 Correct 489 ms 3612 KB Output is correct
11 Correct 180 ms 3584 KB Output is correct
12 Correct 74 ms 3584 KB Output is correct

Subtask #3
0 / 30.0

# Verdict Execution time Memory Grader output
1 Execution timed out 4035 ms 98808 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2688 KB Output is correct
2 Correct 2 ms 2688 KB Output is correct
3 Correct 2 ms 2688 KB Output is correct
4 Correct 2 ms 2688 KB Output is correct
5 Correct 2 ms 2688 KB Output is correct
6 Correct 2 ms 2688 KB Output is correct
7 Correct 480 ms 3704 KB Output is correct
8 Correct 48 ms 3584 KB Output is correct
9 Correct 52 ms 3584 KB Output is correct
10 Correct 489 ms 3612 KB Output is correct
11 Correct 180 ms 3584 KB Output is correct
12 Correct 74 ms 3584 KB Output is correct
13 Execution timed out 4035 ms 98808 KB Time limit exceeded
14 Halted 0 ms 0 KB -