oj.uz

Submission #734872

# Submission time Handle Problem Language Result Execution time Memory
734872 2023-05-03T07:49:03 Z SanguineChameleon Toll (APIO13_toll) C++17
100 / 100
 2189 ms 15460 KB 
#include <bits/stdc++.h>
using namespace std;
 
void just_do_it();
 
int main() {
	#ifdef KAMIRULEZ
		freopen("kamirulez.inp", "r", stdin);
		freopen("kamirulez.out", "w", stdout);
	#endif
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	just_do_it();
	return 0;
}
 
struct edge {
	int u, v, w;
};
 
bool operator<(edge E1, edge E2) {
	return E1.w < E2.w;
};
 
const int inf = 1e9 + 20;
const int maxN = 1e5 + 20;
const int maxM = 3e5 + 20;
const int maxK = 25;

long long cnt[maxN];
vector<pair<int, int>> adj[maxN];
long long sum[maxN];
int par[maxN];
int mi[maxN];
int depth[maxN];
edge edges[maxM];
bool flag1[maxM];
bool flag2[maxM];
int color[maxN];
vector<int> extra;
vector<int> colors;
int N, M, K;

void reset() {
	for (int i = 1; i <= N; i++) {
		par[i] = 0;
		depth[i] = 0;
	}
}

int root(int u) {
	if (!par[u]) {
		return u;
	}
	return (par[u] = root(par[u]));
}

bool update(int u, int v) {
	int ru = root(u);
	int rv = root(v);
	if (ru == rv) {
		return false;
	}
	if (depth[ru] > depth[rv]) {
		swap(ru, rv);
	}
	par[ru] = rv;
	if (depth[ru] == depth[rv]) {
		depth[rv]++;
	}
	return true;
}

void dfs1(int u, int p) {
	for (auto e: adj[u]) {
		int v = e.first;
		if (v == p) {
			continue;
		}
		par[v] = u;
		depth[v] = depth[u] + 1;
		dfs1(v, u);
	}
}

long long dfs2(int u, int p) {
	long long res = 0;
	sum[u] = cnt[u];
	for (auto e: adj[u]) {
		int v = e.first;
		int id = e.second;
		if (v == p) {
			continue;
		}
		res += dfs2(v, u);
		if (id >= M) {
			res += sum[v] * mi[v];
		}
		sum[u] += sum[v];
	}
	return res;
}

void update(int u, int v, int w) {
	if (depth[u] < depth[v]) {
		swap(u, v);
	}
	while (depth[u] != depth[v]) {
		mi[u] = min(mi[u], w);
		u = par[u];
	}
	while (u != v) {
		mi[u] = min(mi[u], w);
		mi[v] = min(mi[v], w);
		u = par[u];
		v = par[v];
	}
}

long long solve(int h) {
	for (auto u: colors) {
		par[u] = 0;
		depth[u] = 0;
		adj[u].clear();
		mi[u] = inf;
	}
	for (int i = 0; i < K; i++) {
		if ((h >> i) & 1) {
			int u = color[edges[M + i].u];
			int v = color[edges[M + i].v];
			if (update(u, v)) {
				adj[u].emplace_back(v, M + i);
				adj[v].emplace_back(u, M + i);
			}
			else {
				return -1;
			}
		}
	}
	vector<int> q;
	for (auto i: extra) {
		int u = color[edges[i].u];
		int v = color[edges[i].v];
		if (update(u, v)) {
			adj[u].emplace_back(v, i);
			adj[v].emplace_back(u, i);
		}
		else {
			q.emplace_back(i);
		}
	}
	depth[color[1]] = 0;
	dfs1(color[1], -1);
	for (auto i: q) {
		int u = color[edges[i].u];
		int v = color[edges[i].v];
		int w = edges[i].w;
		update(u, v, w);
	}
	return dfs2(color[1], -1);
}

void just_do_it() {
	cin >> N >> M >> K;
	for (int i = 0; i < M; i++) {
		cin >> edges[i].u >> edges[i].v >> edges[i].w;
	}
	for (int i = M; i < M + K; i++) {
		cin >> edges[i].u >> edges[i].v;
		edges[i].w = 0;
	}
	for (int i = 1; i <= N; i++) {
		cin >> cnt[i];
	}
	sort(edges, edges + M);
	reset();
	for (int i = 0; i < M; i++) {
		flag1[i] = update(edges[i].u, edges[i].v);
	}
	reset();
	for (int i = M; i < M + K; i++) {
		update(edges[i].u, edges[i].v);
	}
	for (int i = 0; i < M; i++) {
		flag2[i] = update(edges[i].u, edges[i].v);
	}
	reset();
	for (int i = 0; i < M; i++) {
		if (flag1[i]) {
			if (flag2[i]) {
				update(edges[i].u, edges[i].v);
			}
			else {
				extra.emplace_back(i);
			}
		}
	}
	for (int i = 1; i <= N; i++) {
		color[i] = root(i);
		if (i == color[i]) {
			colors.emplace_back(i);
		}
		else {
			cnt[color[i]] += cnt[i];
		}
	}
	reset();
	long long res = 0;
	for (int h = 0; h < (1 << K); h++) {
		res = max(res, solve(h));
	}
	cout << res;
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct
7 Correct 159 ms 9032 KB Output is correct
8 Correct 181 ms 15276 KB Output is correct
9 Correct 183 ms 15272 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 3 ms 2684 KB Output is correct
4 Correct 3 ms 2644 KB Output is correct
5 Correct 6 ms 2772 KB Output is correct
6 Correct 5 ms 2764 KB Output is correct
7 Correct 159 ms 9032 KB Output is correct
8 Correct 181 ms 15276 KB Output is correct
9 Correct 183 ms 15272 KB Output is correct
10 Correct 1550 ms 15368 KB Output is correct
11 Correct 2189 ms 15440 KB Output is correct
12 Correct 2102 ms 15460 KB Output is correct