Submission #287594

#TimeUsernameProblemLanguageResultExecution timeMemory
287594NamnamseoToll (APIO13_toll)C++17
16 / 100
1 ms512 KiB
#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; }
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...