Submission #45437

#	Time	Username	Problem	Language	Result	Execution time	Memory
45437		Noam527	Chase (CEOI17_chase)	C++11	0 / 100	4022 ms	209880 KiB

chase

#include <iostream>
#include <vector>
#include <algorithm>
#include <map>
#include <unordered_map>
#include <set>
#include <unordered_set>
#include <string>
#include <time.h>
#include <stack>
#include <queue>
#include <random>
#include <fstream>
#define endl '\n'
#define flush fflush(stdout), cout.flush()
#define fast ios::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define debug cout << "ok" << endl
#define finish(x) return cout << x << endl, 0
typedef long long ll;
typedef long double ldb;
const int md = 1e9 + 7, inf = 1e9 + 7;
const ll hs = 199;
const ldb eps = 1e-9, pi = acos(-1);
using namespace std;

struct edge {
	int to;
	ll dp[101] = {};
	edge(int tt = 0, ll initial = 0) {
		to = tt;
		dp[0] = initial;
	}
	ll& operator [] (const int k) {
		return dp[k];
	}
};

const int maxn = 1e5 + 1;

int n, v;
ll p[maxn], np[maxn] = {};
vector<ll> mx2[maxn]; // ew. {maxvalue, 2nd maxvalue, vertex of maxvalue
vector<vector<edge>> g;

void update(vector<ll> &aa, pair<ll, int> bb) {
	if (bb.first >= aa[0]) {
		aa[1] = aa[0];
		aa[0] = bb.first;
		aa[2] = bb.second;
	}
	else aa[1] = max(aa[1], bb.first);
}

void stage(int k) {
	for (int i = 0; i < n; i++) mx2[i] = { (ll)-9e18, (ll)-9e18, -1 };
	for (int i = 0; i < n; i++)
		for (auto &j : g[i])
			update(mx2[j.to], { j[k - 1], i });

	for (int i = 0; i < n; i++)
		for (auto &j : g[i]) {
			if (mx2[i][2] == j.to) j[k] = mx2[i][1];
			else j[k] = mx2[i][0];
			j[k] += np[j.to];
		}
}

ll answer() {
	ll rtn = -9e18;
	for (auto &i : g) for (auto &j : i) rtn = max(rtn, j[v - 1] + p[j.to]);
	return rtn;
}

void show(int k) {
	for (int i = 0; i < n; i++)
		for (auto &j : g[i])
			cout << "from " << i << " to " << j.to << " = " << j[k] << endl;
}

int main() {
	fast;
	cin >> n >> v;
	for (int i = 0; i < n; i++) cin >> p[i];
	g.resize(n);
	for (int i = 0, u, v; i < n - 1; i++) {
		cin >> u >> v;
		--u, --v;
		g[u].push_back(edge(v));
		g[v].push_back(edge(u));
		np[u] += p[v];
		np[v] += p[u];
	}
	for (int i = 0; i < n; i++) np[i] -= p[i];
	for (auto &i : g) for (auto &j : i) j[0] = np[j.to];
	for (int i = 1; i < v; i++) stage(i);
	cout << answer() << endl;
}

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