Submission #734736

#	Time	Username	Problem	Language	Result	Execution time	Memory
734736		SanguineChameleon	Toll (APIO13_toll)	C++17	16 / 100	10 ms	4948 KiB

toll

#include <bits/stdc++.h>
using namespace std;

void just_do_it();

int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}

struct edge {
	int u, v, w;
};

bool operator<(edge E1, edge E2) {
	return E1.w < E2.w;
};

const int maxN = 1e5 + 20;
const int maxM = 3e5 + 20;
const int maxK = 25;

int a[maxN];
set<pair<int, int>> adj[maxN];
long long cnt[maxN];
int par[maxN];
int depth[maxN];
edge edges[maxM];
int N, M, K;

int root(int u) {
	if (!par[u]) {
		return u;
	}
	return (par[u] = root(par[u]));
}

bool update(int u, int v) {
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		return false;
	}
	if (depth[ru] > depth[rv]) {
		swap(ru, rv);
	}
	par[ru] = rv;
	if (depth[ru] == depth[rv]) {
		depth[rv]++;
	}
	return true;
}

int get(int u, int p, int v) {
	for (auto e: adj[u]) {
		if (e.first == p) {
			continue;
		}
		if (e.first == v) {
			return e.second;
		}
		int res = get(e.first, u, v);
		if (res != -1) {
			if (edges[e.second].w > edges[res].w) {
				res = e.second;
			}
			return res;
		}
	}
	return -1;
}

long long sum;

void dfs(int u, int p) {
	cnt[u] = a[u];
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (v == p) {
			continue;
		}
		dfs(v, u);
		if (id >= M) {
			sum += cnt[v] * -edges[id].w;
		}
		cnt[u] += cnt[v];
	}
}

long long solve(int h) {
	for (int i = 1; i <= N; i++) {
		par[i] = 0;
		depth[i] = 0;
		adj[i].clear();
	}
	for (int i = 0; i < M; i++) {
		int u = edges[i].u;
		int v = edges[i].v;
		if (update(u, v)) {
			adj[u].emplace(v, i);
			adj[v].emplace(u, i);
		} 
	}
	for (int i = 0; i < K; i++) {
		edges[M + i].w = -1;
	}
	for (int i = 0; i < K; i++) {
		if ((h >> i) & 1) {
			int u = edges[M + i].u;
			int v = edges[M + i].v;
			int best = get(u, -1, v);
			if (best == -1 || best >= M) {
				return -1;
			}
			edges[M + i].w = -edges[best].w;
			adj[u].emplace(v, M + i);
			adj[v].emplace(u, M + i);
			u = edges[best].u;
			v = edges[best].v;
			adj[u].erase(make_pair(v, best));
			adj[v].erase(make_pair(u, best));
		}
	}
	sum = 0;
	dfs(1, -1);
	return sum;
}

void just_do_it() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
	}
	for (int i = M; i < M + K; i++) {
		cin >> edges[i].u >> edges[i].v;
	}
	for (int i = 1; i <= N; i++) {
		cin >> a[i];
	}
	sort(edges, edges + M);
	long long res = 0;
	for (int h = 0; h < (1 << K); h++) {
		res = max(res, solve(h));
	}
	cout << res;
}

• Subtask 1: 16 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22