Submission #536550

#	Time	Username	Problem	Language	Result	Execution time	Memory
536550		Asymmetry	Chase (CEOI17_chase)	C++17	100 / 100	488 ms	232328 KiB

chase

//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 (stderr)

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 / 20
• Subtask 2: 20 / 20
• Subtask 3: 30 / 30
• Subtask 4: 30 / 30