oj.uz

답안 #261790

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
261790 2020-08-12T05:10:25 Z atoiz 통행료 (APIO13_toll) C++14
56 / 100
 209 ms 13132 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <cassert>
#include <map>
#include <set>
#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[MAXN];
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<pair<int, int>>> updates, tree;
	function<set<pair<int, int>>(int, int, int64_t&)> dfs = [&](int u, int p, int64_t& ans) {
		subtree[u] = weight[u];
		set<pair<int, int>> curSet(updates[u].begin(), updates[u].end());
		// for (auto upd : updates) curSet.insert(upd);
		for (auto e : tree[u]) {
			int v = e.first, spec = e.second;
			if (v == p) continue;
			auto tmpSet = dfs(v, u, ans);

			if (spec) {
				assert(!tmpSet.empty());
				ans += tmpSet.begin()->first * subtree[v];
			}

			for (auto upd : tmpSet) {
				if (curSet.find(upd) == curSet.end()) curSet.insert(upd);
				else curSet.erase(upd);
			}
			subtree[u] += subtree[v];
		}

		return curSet;
	};

	int64_t ans = -1;
	for (int mask = 0; mask < (1 << K); ++mask) {
		tree.assign(C + 1, vector<pair<int, int>>(0));
		updates.assign(C + 1, vector<pair<int, int>>(0));

		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], true), tree[Y[i]].emplace_back(X[i], true); }
		}
		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], false), tree[V[e]].emplace_back(U[e], false);
			} else {
				updates[U[e]].emplace_back(W[e], e);
				updates[V[e]].emplace_back(W[e], e);
			}
		}

		int64_t curAns = 0;
		dfs(1, 0, curAns);
		ans = max(ans, curAns);
	}
	cout << ans << endl;
}

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct

Subtask #3
22.0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Incorrect 209 ms 13132 KB Output isn't correct
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 3 ms 384 KB Output is correct
4 Correct 3 ms 384 KB Output is correct
5 Correct 5 ms 512 KB Output is correct
6 Correct 6 ms 512 KB Output is correct
7 Incorrect 209 ms 13132 KB Output isn't correct
8 Halted 0 ms 0 KB -