oj.uz

Submission #536521

# Submission time Handle Problem Language Result Execution time Memory
536521 2022-03-13T13:22:25 Z Asymmetry Chase (CEOI17_chase) C++17
40 / 100
 4000 ms 95772 KB 
//Autor: Bartłomiej Czarkowski
#include <bits/stdc++.h>
using namespace std;
#ifdef DEBUG
template<class A,class B>auto&operator<<(ostream&o,pair<A,B>p){return o<<'('<<p.first<<", "<<p.second<<')';}
template<class T>auto operator<<(ostream&o,T x)->decltype(x.end(),o){o<<'{';int i=0;for(auto e:x)o<<(", ")+2*!i++<<e;return o<<'}';}
#define debug(x...) cerr<<"["#x"]: ",[](auto...$){((cerr<<$<<"; "),...);}(x),cerr<<'\n'
#else
#define debug(...) {}
#endif

const int N = 101'000;
const int V = 107;
int n, m, a, b;
int t[N];
int pr[N];
long long sum[N];
vector<int> v[N];
long long dp[N][V];

void dfd(int x) {
	for (int i : v[x]) {
		if (i == pr[x]) {
			continue;
		}
		pr[i] = x;
		dfd(i);
	}
}

void dfs(int x) {
	for (int i = 0; i <= m; ++i) {
		dp[x][i] = 0;
	}
	for (int i : v[x]) {
		if (i == pr[x]) {
			continue;
		}
		dfs(i);
		for (int j = 0; j <= m; ++j) {
			dp[x][j] = max(dp[x][j], dp[i][j]);
		}
	}
	for (int j = m; j; --j) {
		dp[x][j] = max(dp[x][j], dp[x][j - 1] + sum[x] - t[pr[x]]);
	}
}

int main() {
	scanf("%d%d", &n, &m);
	for (int i = 1; i <= n; ++i) {
		scanf("%d", &t[i]);
	}
	for (int i = 1; i < n; ++i) {
		scanf("%d%d", &a, &b);
		v[a].push_back(b);
		v[b].push_back(a);
	}
	for (int i = 1; i <= n; ++i) {
		for (int j : v[i]) {
			sum[i] += t[j];
		}
	}
	long long odp = 0;
	for (int i = 1; i <= n; ++i) {
		pr[i] = 0;
		dfd(i);
		dfs(i);
		for (int j = 0; j <= m; ++j) {
			odp = max(odp, dp[i][j]);
		}
	}
	printf("%lld\n", odp);
	return 0;
}

Compilation message

chase.cpp: In function 'int main()':
chase.cpp:50:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   50 |  scanf("%d%d", &n, &m);
      |  ~~~~~^~~~~~~~~~~~~~~~
chase.cpp:52:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   52 |   scanf("%d", &t[i]);
      |   ~~~~~^~~~~~~~~~~~~
chase.cpp:55:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |   scanf("%d%d", &a, &b);
      |   ~~~~~^~~~~~~~~~~~~~~~

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 272 ms 3624 KB Output is correct
8 Correct 45 ms 3628 KB Output is correct
9 Correct 35 ms 3580 KB Output is correct
10 Correct 285 ms 3496 KB Output is correct
11 Correct 126 ms 3580 KB Output is correct
12 Correct 71 ms 3580 KB Output is correct

Subtask #3
0 / 30.0

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

Subtask #4
0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2644 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 2 ms 2692 KB Output is correct
4 Correct 2 ms 2644 KB Output is correct
5 Correct 1 ms 2644 KB Output is correct
6 Correct 2 ms 2644 KB Output is correct
7 Correct 272 ms 3624 KB Output is correct
8 Correct 45 ms 3628 KB Output is correct
9 Correct 35 ms 3580 KB Output is correct
10 Correct 285 ms 3496 KB Output is correct
11 Correct 126 ms 3580 KB Output is correct
12 Correct 71 ms 3580 KB Output is correct
13 Execution timed out 4064 ms 95772 KB Time limit exceeded
14 Halted 0 ms 0 KB -