oj.uz

Submission #46967

# Submission time Handle Problem Language Result Execution time Memory
46967 2018-04-25T14:43:02 Z aome Toll (APIO13_toll) C++17
100 / 100
 2205 ms 25008 KB 
#include <bits/stdc++.h>

using namespace std;

const int N = 100005;
const int INF = 1e9;

struct Edge {
	int u, v, w;

	bool operator < (const Edge& rhs) const {
		return w < rhs.w;
	}
};

int n, m, q;
int sz;
int par[N];
int a[N];
int in[N];
int cost[50];
int high[50];
long long sum[50];
long long f[50];
vector<int> G[N];
pair<int, int> b[50];
pair<int, int> up[50];
vector<Edge> E1;
vector<Edge> E2;
vector<Edge> E3;
vector< pair<int, int> > G2[50];

int find(int u) { return u == par[u] ? u : par[u] = find(par[u]); }

bool join(int u, int v) { u = find(u), v = find(v), par[u] = v; return u != v; }

void dfs1(int u, int p) {
	in[u] = sz, sum[sz] += a[u];
	for (auto v : G[u]) if (v != p) dfs1(v, u);
}

void build() {
	for (int i = 1; i <= n; ++i) par[i] = i;
	sort(E1.begin(), E1.end());
	for (auto i : E1) {
		if (join(i.u, i.v)) E2.push_back(i);
	}
	// cout << "#E2\n";
	// for (auto i : E2) cout << i.u << ' ' << i.v << ' ' << i.w << '\n';
	for (int i = 1; i <= n; ++i) par[i] = i;	
	for (int i = 0; i < q; ++i) join(b[i].first, b[i].second);
	for (auto i : E2) {
		if (!join(i.u, i.v)) E3.push_back(i);
		else G[i.u].push_back(i.v), G[i.v].push_back(i.u);
	}
	// cout << "#E3\n";
	// for (auto i : E3) cout << i.u << ' ' << i.v << ' ' << i.w << '\n'; 
	for (int i = 1; i <= n; ++i) in[i] = -1;
	for (int i = 1; i <= n; ++i) {
		if (in[i] == -1) dfs1(i, i), sz++;
	}
}

void dfs2(int u, int p) {
	f[u] = sum[u];
	for (auto v : G2[u]) if (v.first != p) {
		up[v.first] = {u, v.second};
		high[v.first] = high[u] + 1, dfs2(v.first, u), f[u] += f[v.first];
	}
}

long long solve(int mask) {
	for (int i = 0; i < sz; ++i) par[i] = i, G2[i].clear();
	for (int i = 0; i < q; ++i) {
		if (mask >> i & 1) {
			int u = b[i].first, v = b[i].second;
			if (!join(in[u], in[v])) return 0;
			cost[i] = INF;
			G2[in[u]].push_back({in[v], i});
			G2[in[v]].push_back({in[u], i});
		}
	}
	vector<Edge> buffer;
	for (auto i : E3) {
		if (join(in[i.u], in[i.v])) {
			G2[in[i.u]].push_back({in[i.v], -1});
			G2[in[i.v]].push_back({in[i.u], -1});			
		}
		else buffer.push_back(i);
	}
	high[in[1]] = 0, dfs2(in[1], in[1]);
	for (auto i : buffer) {
		int u = in[i.u], v = in[i.v];
		if (high[u] > high[v]) swap(u, v);
		while (high[v] != high[u]) {
			int id = up[v].second; v = up[v].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
		}
		while (u != v) {
			int id;
			id = up[v].second, v = up[v].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
			id = up[u].second, u = up[u].first;
			if (id != -1) cost[id] = min(cost[id], i.w);
		}
	}
	long long ret = 0;
	for (int i = 0; i < q; ++i) {
		if (mask >> i & 1) {
			int u = in[b[i].first], v = in[b[i].second];
			if (high[u] > high[v]) swap(u, v);
			ret += 1LL * cost[i] * f[v];
		}
	}
	return ret;
}

int main() {
	ios::sync_with_stdio(false);
	cin >> n >> m >> q;
	for (int i = 1; i <= m; ++i) {
		int u, v, w; cin >> u >> v >> w;
		E1.push_back({u, v, w});
	}
	for (int i = 0; i < q; ++i) cin >> b[i].first >> b[i].second;
	for (int i = 1; i <= n; ++i) cin >> a[i];
	build();
	long long res = 0;
	for (int i = 0; i < (1 << q); ++i) res = max(res, solve(i));
	cout << res;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2860 KB Output is correct
4 Correct 6 ms 2860 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2860 KB Output is correct
4 Correct 6 ms 2860 KB Output is correct
5 Correct 7 ms 3080 KB Output is correct
6 Correct 8 ms 3100 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2860 KB Output is correct
4 Correct 6 ms 2860 KB Output is correct
5 Correct 7 ms 3080 KB Output is correct
6 Correct 8 ms 3100 KB Output is correct
7 Correct 272 ms 11928 KB Output is correct
8 Correct 261 ms 12040 KB Output is correct
9 Correct 263 ms 12128 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2684 KB Output is correct
2 Correct 4 ms 2788 KB Output is correct
3 Correct 4 ms 2860 KB Output is correct
4 Correct 6 ms 2860 KB Output is correct
5 Correct 7 ms 3080 KB Output is correct
6 Correct 8 ms 3100 KB Output is correct
7 Correct 272 ms 11928 KB Output is correct
8 Correct 261 ms 12040 KB Output is correct
9 Correct 263 ms 12128 KB Output is correct
10 Correct 1816 ms 12160 KB Output is correct
11 Correct 2091 ms 18504 KB Output is correct
12 Correct 2205 ms 25008 KB Output is correct