oj.uz

Submission #261803

# Submission time Handle Problem Language Result Execution time Memory
261803 2020-08-12T05:31:19 Z atoiz Toll (APIO13_toll) C++14
100 / 100
 2253 ms 13944 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], Z[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<pair<int, int>>> tree(C + 1);
	vector<int> par(C + 1), prvID(C + 1), dep(C + 1), inTree(((int) addIDs.size()));
	function<void(int, int)> dfs = [&](int u, int p) {
		subtree[u] = weight[u];
		for (auto e : tree[u]) {
			int v = e.first, id = e.second;
			if (v == p) { par[u] = v, prvID[u] = id; 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, prvID[u] = -1;
		for (int i = 0; i < K; ++i) Z[i] = 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]].emplace_back(Y[i], i), tree[Y[i]].emplace_back(X[i], 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]].emplace_back(V[e], -1), tree[V[e]].emplace_back(U[e], -1);
			}
		}
		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]) if (~prvID[u]) Z[prvID[u]] = min(Z[prvID[u]], w);
			for (; u != v; u = par[u], v = par[v]) {
				if (~prvID[u]) Z[prvID[u]] = min(Z[prvID[u]], w);
				if (~prvID[v]) Z[prvID[v]] = min(Z[prvID[v]], w);
			}
		}

		int64_t curAns = 0;
		for (int u = 1; u <= C; ++u) if (~prvID[u]) curAns += Z[prvID[u]] * subtree[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 2 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 2 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 4 ms 512 KB Output is correct

Subtask #4
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 2 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 4 ms 512 KB Output is correct
7 Correct 250 ms 8440 KB Output is correct
8 Correct 240 ms 8568 KB Output is correct
9 Correct 244 ms 8568 KB Output is correct

Subtask #5
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 2 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 4 ms 512 KB Output is correct
7 Correct 250 ms 8440 KB Output is correct
8 Correct 240 ms 8568 KB Output is correct
9 Correct 244 ms 8568 KB Output is correct
10 Correct 1819 ms 8044 KB Output is correct
11 Correct 2224 ms 7452 KB Output is correct
12 Correct 2253 ms 13944 KB Output is correct