Submission #536514

#	Time	Username	Problem	Language	Result	Execution time	Memory
536514		Asymmetry	Chase (CEOI17_chase)	C++17	0 / 100	4057 ms	14148 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 par {
	long long x;
	int y;
	friend bool operator < (par p, par q) {
		return p.y < q.y || (p.y == q.y && p.x < q.x);
	}
};

struct info {
	par on, off;
};

const int N = 101'000;
int n, m, a, b, kara;
int t[N];
int pr[N];
long long sum[N];
vector<int> v[N];
par ret;
par dp[N]; // zakładamy, że zaczynamy w X

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

void dfs(int x) {
	dp[x] = {0, 0};
	for (int i : v[x]) {
		if (i == pr[x]) {
			continue;
		}
		dfs(i);
		dp[x] = max(dp[x], dp[i]);
	}
	if (sum[x] >= kara) {
		dp[x].x += sum[x] - t[pr[x]] - kara;
		++dp[x].y;
	}
}

par check(int x) {
	kara = x;
	ret.x = -1e18;
	ret.y = 0;
	for (int i = 1; i <= n; ++i) {
		pr[i] = 0;
		dfd(i);
		dfs(i);
		ret = max(ret, dp[i]);
	}
	return ret;
}

int main() {
	scanf("%d%d", &n, &m);
	long long mx = 0;
	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);
	}
	dfd(1);
	for (int i = 1; i <= n; ++i) {
		for (int j : v[i]) {
			sum[i] += t[j];
		}
		mx = max(mx, sum[i]);
	}
	long long bp = 0, bk = mx, bs;
	while (bk - bp > 1) {
		bs = (bp + bk) / 2;
		par w = check(bs);
		if (w.y >= m) {
			bp = bs;
		}
		else {
			bk = bs;
		}
	}
	par w = check(bp);
	printf("%lld\n", w.x + (long long)bp * m);
	return 0;
}

Compilation message (stderr)

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

• Subtask 1: 0 / 20
• Subtask 2: 0 / 20
• Subtask 3: 0 / 30
• Subtask 4: 0 / 30