oj.uz

Submission #346438

# Submission time Handle Problem Language Result Execution time Memory
346438 2021-01-09T16:58:36 Z srvlt Toll (APIO13_toll) C++14
16 / 100
 1 ms 492 KB 
#include <bits/stdc++.h>
#define ll long long
#define pb push_back
#define all(x) begin(x), end(x)
using namespace std;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int n0 = 10, k0 = 10, inf = 1e6 + 123;
int n, m, k, val[n0], mx, sz[n0];
vector <array <int, 2>> g[n0];

struct DSU {
	int p[n0], sz[n0];
	void init(int v) {
		p[v] = v, sz[v] = 1;
	}
	int find(int v) {
		if (v == p[v]) return v;
		return p[v] = find(p[v]);
	}
	bool merge(int v, int u) {
		v = find(v), u = find(u);
		if (v == u) return 0;
		if (sz[v] < sz[u]) swap(v, u);
		p[u] = v, sz[v] += sz[u];
		return 1;
	}
};
DSU mst;

int dfs(int v, int p, int w, int u) {
	int res = -inf;
	if (v == u)
		return w;
	for (auto & i : g[v]) {
		if (i[0] == p) continue;
		res = max(res, dfs(i[0], v, i[1], u));
	}
	if (res != -inf)
		res = max(res, w);
	return res;
}

ll ans;
void go(int v, int p) {
	sz[v] = val[v];
	for (auto & i : g[v]) {
		if (i[0] == p) continue;
		go(i[0], v);
		sz[v] += sz[i[0]];
		if (i[1] == mx)
			ans = (ll)mx * sz[i[0]];
	}
}

int main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m >> k;
	vector <array <int, 3>> init, edges;
	for (int i = 0; i < m; i++) {
		int a, b, c; cin >> a >> b >> c; a--, b--;
		init.pb({c, a, b});
	}
	sort(all(init));
	for (int i = 0; i < n; i++) mst.init(i);
	for (auto & i : init) {
		int a = i[1], b = i[2], c = i[0];
		if (mst.merge(a, b)) g[a].pb({b, c}), g[b].pb({a, c}), edges.pb({c, a, b});
	}
	vector <array <int, 2>> extra;
	for (int i = 0; i < k; i++) {
		int a, b; cin >> a >> b; a--, b--;
		extra.pb({a, b});
	}
	for (int i = 0; i < n; i++) cin >> val[i];
	int v = extra[0][0], u = extra[0][1];
	mx = dfs(v, -1, 0, u);
	for (int i = 0; i < (int)edges.size(); i++) {
		if (edges[i][0] == mx) {
			edges.erase(begin(edges) + i);
			break;
		}
	}
	edges.pb({mx, v, u});
	go(1, 1);
	cout << ans;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 364 KB Output is correct
3 Runtime error 1 ms 492 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Halted 0 ms 0 KB -