oj.uz

Submission #734867

# Submission time Handle Problem Language Result Execution time Memory
734867 2023-05-03T07:38:31 Z SanguineChameleon Toll (APIO13_toll) C++17
56 / 100
 2500 ms 20832 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];
int N, M, K;

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 (int i = 1; i <= N; i++) {
		par[i] = 0;
		depth[i] = 0;
		adj[i].clear();
		mi[i] = inf;
	}
	for (int i = 0; i < K; i++) {
		if ((h >> i) & 1) {
			int u = edges[M + i].u;
			int v = 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> extra;
	for (int i = 0; i < M; i++) {
		int u = edges[i].u;
		int v = edges[i].v;
		if (update(u, v)) {
			adj[u].emplace_back(v, i);
			adj[v].emplace_back(u, i);
		}
		else {
			extra.emplace_back(i);
		}
	}
	depth[1] = 0;
	dfs1(1, -1);
	for (auto i: extra) {
		int u = edges[i].u;
		int v = edges[i].v;
		int w = edges[i].w;
		update(u, v, w);
	}
	return dfs2(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);
	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 3 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 3 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 4 ms 2704 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 4 ms 2704 KB Output is correct
5 Correct 457 ms 2920 KB Output is correct
6 Correct 199 ms 2916 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 4 ms 2704 KB Output is correct
5 Correct 457 ms 2920 KB Output is correct
6 Correct 199 ms 2916 KB Output is correct
7 Execution timed out 2572 ms 20832 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 2772 KB Output is correct
2 Correct 2 ms 2644 KB Output is correct
3 Correct 5 ms 2644 KB Output is correct
4 Correct 4 ms 2704 KB Output is correct
5 Correct 457 ms 2920 KB Output is correct
6 Correct 199 ms 2916 KB Output is correct
7 Execution timed out 2572 ms 20832 KB Time limit exceeded
8 Halted 0 ms 0 KB -