Submission #208876

#	Time	Username	Problem	Language	Result	Execution time	Memory
208876		atoiz	Toll (APIO13_toll)	C++14	16 / 100	5 ms	376 KiB

toll

/*input
5 4 1
1 2 5
2 3 7
3 4 6
4 5 9
3 5
1 10 100 1000 10000

5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/

#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>

using namespace std;

const int MAXN = 1e5 + 6, MAXM = 3e5 + 5, MAXK = 22;
const int INF = 1e8;

struct edge_t
{ 
	int u, v, c; 
	edge_t(int _u = 0, int _v = 0, int _c = 0):
		u(_u), v(_v), c(_c) {}
};

struct dsu_t
{
	int N;
	vector<int> vec;

	void init(int _N)
	{
		N = _N;
		vec.resize(N + 1);
		for (int i = 1; i <= N; ++i) vec[i] = -1;
	}

	int root(int x)
	{
		return (vec[x] < 0 ? x : vec[x] = root(vec[x]));
	}

	bool same(int x, int y)
	{ return root(x) == root(y); }

	void join(int x, int y)
	{
		x = root(x), y = root(y);
		if (x == y) return;
		if (vec[x] > vec[y]) swap(x, y);
		vec[x] += vec[y];
		vec[y] = x;
	}
};

int N, M, K, C = 0;
int comp_id[MAXN];
int64_t P[MAXN], comp_weight[MAXK], subtree[MAXK];
vector<edge_t> edges, extra, comp_edges, copy_edges;
dsu_t comp_dsu;
int comp_dist[MAXK][MAXK];
bool weak_edge[MAXM];
vector<int> tree[MAXK];

template <typename T>
void minimize(T &x, T y)
{ x = (x < y ? x : y); }

template <typename T>
void maximize(T &x, T y)
{ x = (x > y ? x : y); }

void dfs_tree(int u, int p)
{
	subtree[u] = comp_weight[u];
	for (int v : tree[u]) {
		if (v != p) {
			dfs_tree(v, u);
			subtree[u] += subtree[v];
		}
	}
}

void get_dist(int root, int u, int p, int mx)
{
	comp_dist[root][u] = mx;
	for (auto &e : comp_edges) {
		int v = -1;
		if (e.u == u) v = e.v;
		else if (e.v == u) v = e.u;
		else continue;

		if (v != p) get_dist(root, v, u, max(mx, e.c));
	}
}

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> K;
	edges.resize(M);
	for (auto &e : edges) cin >> e.u >> e.v >> e.c;
	sort(edges.begin(), edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });

	extra.resize(K);
	for (auto &e : extra) cin >> e.u >> e.v;

	for (int i = 1; i <= N; ++i) cin >> P[i];

	comp_dsu.init(N);
	for (auto &e : extra) comp_dsu.join(e.u, e.v);
	for (int i = 0; i < M; ++i) {
		auto &e = edges[i];
		if (not comp_dsu.same(e.u, e.v)) {
			comp_dsu.join(e.u, e.v);
			weak_edge[i] = true;
		}
	}

	comp_dsu.init(N);
	for (int i = 0; i < M; ++i) {
		if (weak_edge[i]) {
			comp_dsu.join(edges[i].u, edges[i].v);
		}
	}

	for (int i = 1; i <= N; ++i) {
		if (comp_dsu.root(i) == i) comp_id[i] = ++C;
	}
	for (int i = 1; i <= N; ++i) {
		if (comp_dsu.root(i) != i) comp_id[i] = comp_id[comp_dsu.root(i)];
	}
	// for (int i = 1; i <= N; ++i) cout << "id " << i << ": " << comp_id[i] << endl;
	for (auto &e : extra) e.u = comp_id[e.u], e.v = comp_id[e.v];
	assert(C <= K + 1);

	for (int i = 1; i <= N; ++i) {
		comp_weight[comp_id[i]] += P[i];
	}
	// for (int i = 1; i <= C; ++i) cout << "weight " << i << ": " << comp_weight[i] << endl;

	for (int u = 1; u <= C; ++u) {
		for (int v = 1; v <= C; ++v) {
			comp_dist[u][v] = INF;
		}
	}
	for (auto &e : edges) {
		minimize(comp_dist[comp_id[e.u]][comp_id[e.v]], e.c);
		minimize(comp_dist[comp_id[e.v]][comp_id[e.u]], e.c);
	}

	for (int u = 2; u <= C; ++u) {
		for (int v = 1; v < u; ++v) {
			if (comp_dist[u][v] != INF) {
				comp_edges.emplace_back(u, v, comp_dist[u][v]);
			}
		}
	}
	sort(comp_edges.begin(), comp_edges.end(), [&](edge_t &lhs, edge_t &rhs) { return lhs.c < rhs.c; });
	comp_dsu.init(C);
	for (auto &e : comp_edges) {
		if (not comp_dsu.same(e.u, e.v)) {
			copy_edges.push_back(e);
			comp_dsu.join(e.u, e.v);
			// cout << "edge " << e.u << ' ' << e.v << ": " << e.c << endl;
		}
	}
	comp_edges = move(copy_edges);

	for (int u = 1; u <= C; ++u) {
		get_dist(u, u, u, -1);
	}

	for (auto &e : extra) e.c = comp_dist[e.u][e.v];
	// for (auto &e : extra) cout << "extra " << e.u << ' ' << e.v << ": " << e.c << endl;

	return cout << extra[0].c * comp_weight[3 - comp_id[1]] << endl, 0;
	int64_t optimal = 0;
	for (int mask = 0; mask < (1 << K); ++mask) {
		comp_dsu.init(C);
		for (int i = 1; i <= C; ++i) tree[i].clear();

		bool cycle = false;
		for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
			auto &e = extra[i];
			if (comp_dsu.same(e.u, e.v)) {
				cycle = true;
				break;
			}
			comp_dsu.join(e.u, e.v);
			tree[e.u].push_back(e.v);
			tree[e.v].push_back(e.u);
		}
		if (cycle) continue;

		for (auto &e : comp_edges) {
			if (not comp_dsu.same(e.u, e.v)) {
				comp_dsu.join(e.u, e.v);
				tree[e.u].push_back(e.v);
				tree[e.v].push_back(e.u);
			}
		}

		dfs_tree(1, 1);
		int64_t total = 0;
		for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
			auto &e = extra[i];
			total += e.c * min(subtree[e.u], subtree[e.v]);
		}
		// cout << "total " << mask << ": " << total << endl;
		maximize(optimal, total);
	}

	cout << optimal << endl;
}

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