oj.uz

Submission #208900

# Submission time Handle Problem Language Result Execution time Memory
208900 2020-03-12T12:27:19 Z atoiz Toll (APIO13_toll) C++14
100 / 100
 1607 ms 9524 KB 
/*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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 8 ms 508 KB Output is correct
6 Correct 9 ms 504 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 8 ms 508 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 196 ms 9464 KB Output is correct
8 Correct 204 ms 9464 KB Output is correct
9 Correct 211 ms 9464 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 376 KB Output is correct
3 Correct 5 ms 376 KB Output is correct
4 Correct 5 ms 376 KB Output is correct
5 Correct 8 ms 508 KB Output is correct
6 Correct 9 ms 504 KB Output is correct
7 Correct 196 ms 9464 KB Output is correct
8 Correct 204 ms 9464 KB Output is correct
9 Correct 211 ms 9464 KB Output is correct
10 Correct 1211 ms 9524 KB Output is correct
11 Correct 1602 ms 9208 KB Output is correct
12 Correct 1607 ms 9336 KB Output is correct