oj.uz

Submission #261814

# Submission time Handle Problem Language Result Execution time Memory
261814 2020-08-12T05:38:39 Z atoiz Toll (APIO13_toll) C++14
100 / 100
 1946 ms 7672 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <functional>
#include <numeric>

using namespace std;

struct DSU
{
	int N;
	vector<int> A;
	DSU(int _N = 0): N(_N), A(_N + 1, -1) {};
	void reset(int _N) { N = _N, A.assign(N + 1, -1); }
	int get(int u) { return A[u] < 0 ? u : A[u] = get(A[u]); }
	bool same(int u, int v) { return get(u) == get(v); }
	void join(int u, int v)
	{
		u = get(u), v = get(v);
		if (u == v) return;
		if (A[u] > A[v]) swap(u, v);
		A[u] += A[v], A[v] = u;
	}
};

const int MAXN = 100007, MAXM = 300007, MAXK = 20, INF = 1e8;
int N, M, K, C;
int label[MAXN], P[MAXN];
int U[MAXM], V[MAXM], W[MAXM], flag[MAXM];
int X[MAXK], Y[MAXK];
int64_t weight[MAXN], subtree[MAXN];

int main()
{
	ios_base::sync_with_stdio(0); cin.tie(0);
	cin >> N >> M >> K;
	for (int e = 0; e < M; ++e) cin >> U[e] >> V[e] >> W[e];
	for (int i = 0; i < K; ++i) cin >> X[i] >> Y[i];
	for (int i = 1; i <= N; ++i) cin >> P[i];

	vector<int> lis(M);
	iota(lis.begin(), lis.end(), 0);
	sort(lis.begin(), lis.end(), [&](int i, int j) { return W[i] < W[j]; });

	DSU dsu(N);
	for (int i = 0; i < K; ++i) dsu.join(X[i], Y[i]);
	for (auto &e : lis) if (!dsu.same(U[e], V[e])) dsu.join(U[e], V[e]), flag[e] = true;
	dsu.reset(N);
	for (auto &e : lis) if (flag[e]) dsu.join(U[e], V[e]);
	
	map<int, int> convert;
	for (int u = 1; u <= N; ++u) {
		int cur = dsu.get(u);
		if (convert.find(cur) == convert.end()) convert[cur] = ++C;
		label[u] = convert[cur];
		weight[label[u]] += P[u];
	}
	for (auto &e : lis) U[e] = label[U[e]], V[e] = label[V[e]];
	for (int i = 0; i < K; ++i) X[i] = label[X[i]], Y[i] = label[Y[i]];

	vector<int> addIDs;
	dsu.reset(C);
	for (auto &e : lis) if (!dsu.same(U[e], V[e])) dsu.join(U[e], V[e]), addIDs.push_back(e);

	vector<vector<int>> tree(C + 1);
	vector<int> par(C + 1), val(C + 1), dep(C + 1), inTree(((int) addIDs.size()));
	function<void(int, int)> dfs = [&](int u, int p) {
		subtree[u] = weight[u];
		for (int v : tree[u]) {
			if (v == p) { par[u] = v; continue; }
			dep[v] = dep[u] + 1;
			dfs(v, u);
			subtree[u] += subtree[v];
		}
	};

	int64_t ans = -1;
	for (int mask = 0; mask < (1 << K); ++mask) {
		for (int u = 1; u <= C; ++u) tree[u].clear(), dep[u] = 0, val[u] = INF;

		bool cycle = false;
		dsu.reset(C);
		for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
			if (dsu.same(X[i], Y[i])) { cycle = true; break; }
			else { dsu.join(X[i], Y[i]), tree[X[i]].push_back(Y[i]), tree[Y[i]].push_back(X[i]); }
		}
		if (cycle) continue;

		for (int i = 0; i < ((int) addIDs.size()); ++i) {
			int e = addIDs[i];
			if ((inTree[i] = !dsu.same(U[e], V[e]))) {
				dsu.join(U[e], V[e]), tree[U[e]].push_back(V[e]), tree[V[e]].push_back(U[e]);
			}
		}
		dfs(1, 0);

		for (int i = 0; i < ((int) addIDs.size()); ++i) if (!inTree[i]) {
			int e = addIDs[i];
			int u = U[e], v = V[e], w = W[e];
			if (dep[u] < dep[v]) swap(u, v);
			for (; dep[u] > dep[v]; u = par[u]) val[u] = min(val[u], w);
			for (; u != v; u = par[u], v = par[v]) val[u] = min(val[u], w), val[v] = min(val[v], w);
		}

		int64_t curAns = 0;
		for (int i = 0; i < K; ++i) if ((mask >> i) & 1) {
			int u = X[i], v = Y[i];
			if (u == par[v]) swap(u, v);
			curAns += subtree[u] * val[u];
		}
		ans = max(ans, curAns);
	}
	cout << ans << endl;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 231 ms 7376 KB Output is correct
8 Correct 233 ms 7544 KB Output is correct
9 Correct 233 ms 7544 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 4 ms 512 KB Output is correct
6 Correct 3 ms 512 KB Output is correct
7 Correct 231 ms 7376 KB Output is correct
8 Correct 233 ms 7544 KB Output is correct
9 Correct 233 ms 7544 KB Output is correct
10 Correct 1474 ms 7500 KB Output is correct
11 Correct 1941 ms 7544 KB Output is correct
12 Correct 1946 ms 7672 KB Output is correct