oj.uz

Submission #261818

# Submission time Handle Problem Language Result Execution time Memory
261818 2020-08-12T05:40:24 Z atoiz Toll (APIO13_toll) C++14
100 / 100
 1779 ms 8312 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];

vector<vector<int>> tree;
vector<int> par, val, dep, inTree;
void 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];
	}
};

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);

	tree.resize(C + 1), par.resize(C + 1), val.resize(C + 1), dep.resize(C + 1), inTree.resize((int) addIDs.size());

	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 1 ms 384 KB Output is correct
2 Correct 0 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 1 ms 384 KB Output is correct
2 Correct 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 226 ms 8000 KB Output is correct
8 Correct 262 ms 8056 KB Output is correct
9 Correct 229 ms 8080 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 0 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 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 226 ms 8000 KB Output is correct
8 Correct 262 ms 8056 KB Output is correct
9 Correct 229 ms 8080 KB Output is correct
10 Correct 1347 ms 8312 KB Output is correct
11 Correct 1750 ms 7928 KB Output is correct
12 Correct 1779 ms 8016 KB Output is correct