Submission #46967

#	Time	Username	Problem	Language	Result	Execution time	Memory
46967		aome	Toll (APIO13_toll)	C++17	100 / 100	2205 ms	25008 KiB

toll

#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int INF = 1e9;

struct Edge {
	int u, v, w;

	bool operator < (const Edge& rhs) const {
		return w < rhs.w;
	}
};

int n, m, q;
int sz;
int par[N];
int a[N];
int in[N];
int cost[50];
int high[50];
long long sum[50];
long long f[50];
vector<int> G[N];
pair<int, int> b[50];
pair<int, int> up[50];
vector<Edge> E1;
vector<Edge> E2;
vector<Edge> E3;
vector< pair<int, int> > G2[50];

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

bool join(int u, int v) { u = find(u), v = find(v), par[u] = v; return u != v; }

void dfs1(int u, int p) {
	in[u] = sz, sum[sz] += a[u];
	for (auto v : G[u]) if (v != p) dfs1(v, u);
}

void build() {
	for (int i = 1; i <= n; ++i) par[i] = i;
	sort(E1.begin(), E1.end());
	for (auto i : E1) {
		if (join(i.u, i.v)) E2.push_back(i);
	}
	// cout << "#E2\n";
	// for (auto i : E2) cout << i.u << ' ' << i.v << ' ' << i.w << '\n';
	for (int i = 1; i <= n; ++i) par[i] = i;	
	for (int i = 0; i < q; ++i) join(b[i].first, b[i].second);
	for (auto i : E2) {
		if (!join(i.u, i.v)) E3.push_back(i);
		else G[i.u].push_back(i.v), G[i.v].push_back(i.u);
	}
	// cout << "#E3\n";
	// for (auto i : E3) cout << i.u << ' ' << i.v << ' ' << i.w << '\n'; 
	for (int i = 1; i <= n; ++i) in[i] = -1;
	for (int i = 1; i <= n; ++i) {
		if (in[i] == -1) dfs1(i, i), sz++;
	}
}

void dfs2(int u, int p) {
	f[u] = sum[u];
	for (auto v : G2[u]) if (v.first != p) {
		up[v.first] = {u, v.second};
		high[v.first] = high[u] + 1, dfs2(v.first, u), f[u] += f[v.first];
	}
}

long long solve(int mask) {
	for (int i = 0; i < sz; ++i) par[i] = i, G2[i].clear();
	for (int i = 0; i < q; ++i) {
		if (mask >> i & 1) {
			int u = b[i].first, v = b[i].second;
			if (!join(in[u], in[v])) return 0;
			cost[i] = INF;
			G2[in[u]].push_back({in[v], i});
			G2[in[v]].push_back({in[u], i});
		}
	}
	vector<Edge> buffer;
	for (auto i : E3) {
		if (join(in[i.u], in[i.v])) {
			G2[in[i.u]].push_back({in[i.v], -1});
			G2[in[i.v]].push_back({in[i.u], -1});			
		}
		else buffer.push_back(i);
	}
	high[in[1]] = 0, dfs2(in[1], in[1]);
	for (auto i : buffer) {
		int u = in[i.u], v = in[i.v];
		if (high[u] > high[v]) swap(u, v);
		while (high[v] != high[u]) {
			int id = up[v].second; v = up[v].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
		}
		while (u != v) {
			int id;
			id = up[v].second, v = up[v].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
			id = up[u].second, u = up[u].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
		}
	}
	long long ret = 0;
	for (int i = 0; i < q; ++i) {
		if (mask >> i & 1) {
			int u = in[b[i].first], v = in[b[i].second];
			if (high[u] > high[v]) swap(u, v);
			ret += 1LL * cost[i] * f[v];
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		E1.push_back({u, v, w});
	}
	for (int i = 0; i < q; ++i) cin >> b[i].first >> b[i].second;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build();
	long long res = 0;
	for (int i = 0; i < (1 << q); ++i) res = max(res, solve(i));
	cout << res;
}

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