oj.uz

Submission #261799

# Submission time Handle Problem Language Result Execution time Memory
261799 2020-08-12T05:25:02 Z atoiz Toll (APIO13_toll) C++14
78 / 100
 2500 ms 13912 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;
	vector<int> par, prvID, dep;
	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) {
		tree.assign(C + 1, vector<pair<int, int>>(0));
		dep.assign(C + 1, 0);
		par.resize(C + 1), prvID.assign(C + 1, -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 e : addIDs) if (!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 e : addIDs) {
			if (!dsu.same(U[e], V[e])) dsu.join(U[e], V[e]);
			else {
				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 5 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 5 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 245 ms 7672 KB Output is correct
8 Correct 257 ms 8056 KB Output is correct
9 Correct 244 ms 7928 KB Output is correct

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 2 ms 384 KB Output is correct
4 Correct 2 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 4 ms 512 KB Output is correct
7 Correct 245 ms 7672 KB Output is correct
8 Correct 257 ms 8056 KB Output is correct
9 Correct 244 ms 7928 KB Output is correct
10 Correct 2049 ms 7972 KB Output is correct
11 Execution timed out 2542 ms 13912 KB Time limit exceeded
12 Halted 0 ms 0 KB -