oj.uz

Submission #287594

# Submission time Handle Problem Language Result Execution time Memory
287594 2020-08-31T20:50:05 Z Namnamseo Toll (APIO13_toll) C++17
16 / 100
 1 ms 512 KB 
#include <bits/stdc++.h>
using namespace std;
using ll=long long;
#define rep(i,n) for(int i=0;i<n;++i)
#define rrep(i,n) for(int i=1;i<=n;++i)
#define pb push_back
#define eb emplace_back

int n, m, k;

using t3=tuple<int,int,int>;
using pp=pair<int, int>;

t3 e[30];
struct UF { int p[100010]; void init(int s=n){iota(p+1,p+s+1,1);} int r(int x){return x==p[x]?x:(p[x]=r(p[x])); }
int join(int a,int b){ a=r(a);b=r(b); if(a==b) return 0;p[a]=b;return 1; }} uf;

int s[20];
int u[20];

int dep[20], par[20], us[20];
ll ld[20];
vector<pp> t[20];
void dfs(int x) {
	us[x] = u[x];
	for(auto [y,d]:t[x]) if (y != par[x]) {
		par[y] = x;
		dep[y] = dep[x] + 1;
		ld[y] = ld[x] + d;
		dfs(y);
		us[x] += us[y];
	}
}

int lca(int a, int b) {
	if (dep[a]>dep[b]) return lca(b, a);
	while (dep[b]!=dep[a]) b=par[b];
	while (a!=b) a=par[a], b=par[b];
	return a;
}

int main()
{
	cin >> n >> m >> k;
	assert(k == 1 && n <= 10 && m <= 20);
	rep(i, m) { int a, b, c; cin >> a >> b >> c; e[i] = {c, a, b}; }
	int ka, kb; cin >> ka >> kb;
	rrep(i, n) cin >> u[i];

	sort(e, e+m); uf.init(n); 
	rep(i, m) {
		auto [c, a, b] = e[i];
		if (uf.join(a, b))
			t[a].eb(b, c), t[b].eb(a, c);
	}

	dfs(1);

	int kl = lca(ka, kb);
	ll mdf = 0; int mlo = -1;
	for(int v:{ka, kb}) {
		for(;v != kl; v=par[v]) {
			ll tmp = (ld[v]-ld[par[v]]);
			if (mdf < tmp) {
				mdf = tmp;
				mlo = v;
			}
		}
	}

	cout << (mdf * us[mlo]) << '\n';

	return 0;
}

Subtask #1
16.0 / 16.0

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

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Runtime error 1 ms 512 KB Execution killed with signal 11
4 Halted 0 ms 0 KB -