Submission #1096210

#	Time	Username	Problem	Language	Result	Execution time	Memory
1096210		xnqs	Toll (APIO13_toll)	C++17	0 / 100	0 ms	344 KiB

toll

// the idea is to maximize the number of red edges
// and at the same time maximize their cost,
// and because q is small, we can just iterate over every subset of red edges.
// now that i think about it, it's probably solvable in O(logN*2^q) but idk
// (there's a solution that optimizes this with link cut trees or euler tour trees for sure but thats probably overkill)

#include <iostream>
#include <fstream>
#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <numeric>
#include <functional>

class DSU {
private:
	int n;
	std::vector<int> t;
	std::vector<int> sz;
public:
	DSU(int n): n(n) {
		t.assign(n,0); std::iota(t.begin(),t.end(),0);
		sz.assign(n,1);
	}

	int Find(int k) {
		return ((t[k]==k) ? k : t[k] = Find(t[k]));
	}

	int Unite(int a, int b) {
		int ra = Find(a);
		int rb = Find(b);

		if (ra==rb) {
			return 0;
		}

		if (sz[ra]<sz[rb]) {
			std::swap(ra,rb);
		}

		sz[ra] += sz[rb];
		t[rb] = ra;
		return 1;
	}
};

int gs, edg, q;
int node_val[5005];
std::vector<std::vector<std::pair<int,int>>> adj_list;
std::vector<std::vector<std::pair<int,int>>> adj_list_mst;
std::vector<std::vector<std::tuple<int,int,int>>> adj_list_new_tree;
std::vector<std::tuple<int,int,int>> black_edges;
std::vector<std::pair<int,int>> red_edges;

void build_mst() {
	adj_list_mst.resize(gs+1);
	std::sort(black_edges.begin(),black_edges.end(),[](const std::tuple<int,int,int>& a, const std::tuple<int,int,int>& b) {
		return std::get<2>(a) < std::get<2>(b);
	});

	DSU dsu(gs+1);
	for (const auto& [a, b, c] : black_edges) {
		if (dsu.Unite(a,b)) {
			adj_list_mst[a].emplace_back(b,c);
			adj_list_mst[b].emplace_back(a,c);
		}
	}
}

std::tuple<int,int,int> most_expensive_edge_on_path(int src, int dest) {
	std::vector<int> root(gs+1,-1);
	std::vector<std::tuple<int,int,int>> max(gs+1, std::tuple<int,int,int>(-1,-1,-1));
	std::queue<int> q;

	q.emplace(src);
	root[src] = 0;
	
	q.emplace(dest);
	root[dest] = 1;

	std::tuple<int,int,int> ret(-1,-1,-1);
	while (!q.empty()) {
		int k = q.front();
		q.pop();

		for (const auto& [i, w, t] : adj_list_new_tree[k]) {
			if (root[i]==-1) {
				root[i] = root[k];
				max[i] = std::max(max[i], ((!t) ? std::tuple<int,int,int>(w,k,i) : std::tuple<int,int,int>()));
			}
			else if (root[i]!=root[k]) {
				ret = std::max(std::max(max[i], max[k]), ((!t) ? std::tuple<int,int,int>(w,k,i) : std::tuple<int,int,int>()));
				break;
			}
		}
	}

	return ret;
}

// ok, so first we build the mst of the black edges.
// then, we iterate over the set of selected red edges, and we try to insert them into
// the new cycle in the mst that gets created and break it at the most expensive non-red edge.
// the weight of the red edge now becomes the weight of the most expensive black edge along the path.
int64_t solve(int mask) {
	adj_list_new_tree.clear();
	adj_list_new_tree.resize(gs+1);
	for (int i = 1; i <= gs; i++) {
		for (const auto& [j, w] : adj_list_mst[i]) {
			adj_list_new_tree[i].emplace_back(j,w,0);
		}
	}

	for (int i = 0; i < mask; i++) {
		if (mask&(1<<i)) {
			auto [u, v] = red_edges[i];
			auto [w, a, b] = most_expensive_edge_on_path(u, v);
			if (w==-1) {
				continue;
			}

			adj_list_new_tree[a].erase(std::find(adj_list_new_tree[a].begin(),adj_list_new_tree[a].end(),std::tuple<int,int,int>(b,w,0)));
			adj_list_new_tree[b].erase(std::find(adj_list_new_tree[b].begin(),adj_list_new_tree[b].end(),std::tuple<int,int,int>(a,w,0)));
			adj_list_new_tree[u].emplace_back(v,w,1);
			adj_list_new_tree[v].emplace_back(u,w,1);
		}
	}

	std::vector<int64_t> sub_sz(gs+1,0);
	const std::function<int64_t(int,int)> dfs = [&](int k, int p) {
		int64_t ret = 0;
		sub_sz[k] = node_val[k];
		for (const auto& [i, w, t] : adj_list_new_tree[k]) {
			if (i!=p) {
				ret = std::max(ret, dfs(i,k));
				sub_sz[k] += sub_sz[i];
				if (t) {
					ret = std::max(ret, (int64_t)w*sub_sz[i]);
				}
			}
		}

		return ret;
	};

	return dfs(1,0);
}

int main() {
	std::ios_base::sync_with_stdio(false);
	std::cin.tie(NULL);
	std::cout.tie(NULL);

	std::cin >> gs >> edg >> q;
	adj_list.resize(gs+1);
	for (int i = 0, a, b, c; i < edg; i++) {
		std::cin >> a >> b >> c;
		black_edges.emplace_back(a,b,c);
	}
	for (int i = 0, a, b; i < q; i++) {
		std::cin >> a >> b;
		red_edges.emplace_back(a,b);
	}

	for (int i = 1; i <= gs; i++) {
		std::cin >> node_val[i];
	}

	build_mst();
	int64_t ans = 0;
	for (int mask = 1; mask < (1<<q); mask++) {
		ans = std::max(ans, solve(mask));
	}

	std::cout << ans << "\n";
}

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