Submission #287594

#	Time	Username	Problem	Language	Result	Execution time	Memory
287594		Namnamseo	Toll (APIO13_toll)	C++17	16 / 100	1 ms	512 KiB

toll

#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 / 16
• Subtask 2: 0 / 18
• Subtask 3: 0 / 22
• Subtask 4: 0 / 22
• Subtask 5: 0 / 22