Submission #208900

#	Time	Username	Problem	Language	Result	Execution time	Memory
208900		atoiz	Toll (APIO13_toll)	C++14	100 / 100	1607 ms	9524 KiB

toll

/*input
6 5 3
5 1 1
2 6 2
5 4 3
1 2 4
2 3 5
1 5 
1 6 
4 6 
9 6 6 1 8 6 
 
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], edge_weight[MAXK];
vector<edge_t> edges, extra, comp_edges, copy_edges;
dsu_t comp_dsu;
int comp_dist[MAXK][MAXK], edge_len[MAXK], dep[MAXK], par[MAXK];
bool weak_edge[MAXM], in_tree[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)
{
    par[u] = p;
	subtree[u] = comp_weight[u];
	for (int v : tree[u]) {
		if (v != p) {
            dep[v] = dep[u] + 1;
			dfs_tree(v, u);
			subtree[u] += subtree[v];
		}
	}
}
 
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);
		}
	}
	comp_edges = move(copy_edges);
    assert((int) comp_edges.size() == C - 1);
    assert(comp_dsu.vec[comp_dsu.root(1)] == -C);
 
	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 (int i = 0; i < (int) comp_edges.size(); ++i) {
            auto &e = comp_edges[i];
			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);
                in_tree[i] = true;
			} else in_tree[i] = false;
		}
        assert((int) comp_edges.size() == C - 1);
        assert(comp_dsu.vec[comp_dsu.root(1)] == -C);
 
        dep[comp_id[1]] = 0;
		dfs_tree(comp_id[1], 0);

        for (int i = 1; i <= C; ++i) edge_len[i] = INF;
        for (int i = 0; i < (int) comp_edges.size(); ++i) if (not in_tree[i]) {
            int u = comp_edges[i].u, v = comp_edges[i].v, c = comp_edges[i].c;
            if (dep[u] < dep[v]) swap(u, v);
            while (dep[u] > dep[v]) minimize(edge_len[u], c), u = par[u];
            while (u != v) minimize(edge_len[u], c), minimize(edge_len[v], c), u = par[u], v = par[v];
        }

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

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