oj.uz

Submission #536550

# Submission time Handle Problem Language Result Execution time Memory
536550 2022-03-13T13:56:40 Z Asymmetry Chase (CEOI17_chase) C++17
100 / 100
 488 ms 232328 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

struct node {
	vector<long long> t;
	void res(int x) {
		t.resize(x + 1);
		for (int i = 0; i <= x; ++i) {
			t[i] = 0;
		}
	}
	friend node operator * (node p, node q) {
		int m = p.t.size();
		for (int i = 0; i < m; ++i) {
			p.t[i] = max(p.t[i], q.t[i]);
		}
		return p;
	}
};

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

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

void reroot(int x, node ojc) {
	node dum;
	dum.res(m);
	vector<node> prf;
	prf.push_back(dum);
	for (int i : v[x]) {
		if (i == pr[x]) {
			continue;
		}
		prf.push_back(prf.back() * dp[i]);
	}
	dum = prf.back() * ojc;
	for (int i = m; i; --i) {
		odp = max({odp, dum.t[i], dum.t[i - 1] + sum[x]});
	}
	reverse(v[x].begin(), v[x].end());
	for (int i : v[x]) {
		if (i == pr[x]) {
			continue;
		}
		prf.pop_back();
		dum = prf.back() * ojc;
		for (int j = m; j; --j) {
			dum.t[j] = max(dum.t[j], dum.t[j - 1] + sum[x] - t[i]);
		}
		reroot(i, dum);
		ojc = ojc * dp[i];
	}
}

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];
		}
	}
	dfs(1);
	node dum;
	dum.res(m);
	reroot(1, dum);
	printf("%lld\n", odp);
	return 0;
}

Compilation message

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

Subtask #1
20.0 / 20.0

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

Subtask #2
20.0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 6 ms 5844 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct

Subtask #3
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 463 ms 228884 KB Output is correct
2 Correct 428 ms 230364 KB Output is correct
3 Correct 302 ms 175844 KB Output is correct
4 Correct 139 ms 15036 KB Output is correct
5 Correct 392 ms 92052 KB Output is correct
6 Correct 358 ms 93420 KB Output is correct
7 Correct 407 ms 93652 KB Output is correct

Subtask #4
30.0 / 30.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 4948 KB Output is correct
2 Correct 3 ms 4948 KB Output is correct
3 Correct 3 ms 4948 KB Output is correct
4 Correct 2 ms 4948 KB Output is correct
5 Correct 3 ms 4948 KB Output is correct
6 Correct 2 ms 4948 KB Output is correct
7 Correct 6 ms 7244 KB Output is correct
8 Correct 4 ms 5332 KB Output is correct
9 Correct 3 ms 5204 KB Output is correct
10 Correct 6 ms 5844 KB Output is correct
11 Correct 4 ms 5332 KB Output is correct
12 Correct 4 ms 5204 KB Output is correct
13 Correct 463 ms 228884 KB Output is correct
14 Correct 428 ms 230364 KB Output is correct
15 Correct 302 ms 175844 KB Output is correct
16 Correct 139 ms 15036 KB Output is correct
17 Correct 392 ms 92052 KB Output is correct
18 Correct 358 ms 93420 KB Output is correct
19 Correct 407 ms 93652 KB Output is correct
20 Correct 399 ms 93396 KB Output is correct
21 Correct 155 ms 14972 KB Output is correct
22 Correct 455 ms 93436 KB Output is correct
23 Correct 163 ms 15152 KB Output is correct
24 Correct 407 ms 93436 KB Output is correct
25 Correct 308 ms 175416 KB Output is correct
26 Correct 488 ms 232328 KB Output is correct
27 Correct 455 ms 232188 KB Output is correct