This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#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;
}
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |