oj.uz

Submission #261813

# Submission time Handle Problem Language Result Execution time Memory
261813 2020-08-12T05:37:57 Z atoiz Toll (APIO13_toll) C++14
56 / 100
 224 ms 7416 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[u], 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 1 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 1 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 1 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
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 224 ms 7416 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 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 Incorrect 224 ms 7416 KB Output isn't correct
8 Halted 0 ms 0 KB -