Submission #15934

#TimeUsernameProblemLanguageResultExecution timeMemory
15934myungwooToll (APIO13_toll)C++14
100 / 100
2246 ms7588 KiB
#include <bits/stdc++.h> using namespace std; #define MAXN 100005 #define MAXM 300005 #define pb push_back #define sz(v) ((int)(v).size()) typedef long long lld; int N, M, K, C; int A[MAXN]; int par[MAXN], num[MAXN], H[23], tpar[23]; int up[23]; lld subtree_sz[23], sz[23]; vector <int> con[23], tcon[23], tconv[23]; struct EDGE{ int a, b, c; bool in_mst, is_critical; } E[MAXM], F[21]; int cp(int n){ return par[n] == n ? n : (par[n] = cp(par[n])); } void dfs(int n, int from) { subtree_sz[n] = sz[n]; for (int i=sz(tcon[n]);i--;){ int t = tcon[n][i], v = tconv[n][i]; if (t == from) continue; H[t] = H[n] + 1; up[t] = v; tpar[t] = n; dfs(t, n); subtree_sz[n] += subtree_sz[t]; } } int main() { scanf("%d%d%d", &N, &M, &K); for (int i=1;i<=M;i++) scanf("%d%d%d", &E[i].a, &E[i].b, &E[i].c); for (int i=1;i<=K;i++) scanf("%d%d", &F[i].a, &F[i].b); for (int i=1;i<=N;i++) scanf("%d", A+i); sort(E+1, E+M+1, [](const EDGE &a, const EDGE &b){ return a.c < b.c; }); for (int i=1;i<=N;i++) par[i] = i; for (int i=1;i<=M;i++){ int a = cp(E[i].a), b = cp(E[i].b); if (a == b) continue; par[b] = a; E[i].in_mst = 1; } for (int i=1;i<=N;i++) par[i] = i; for (int i=1;i<=K;i++){ int a = cp(F[i].a), b = cp(F[i].b); par[b] = a; } for (int i=1;i<=M;i++) if (E[i].in_mst){ int a = cp(E[i].a), b = cp(E[i].b); if (a == b) E[i].is_critical = 1; par[b] = a; } for (int i=1;i<=N;i++) par[i] = i; for (int i=1;i<=M;i++) if (E[i].in_mst && !E[i].is_critical){ int a = cp(E[i].a), b = cp(E[i].b); if (a > b) swap(a, b); par[b] = a; } for (int i=1;i<=N;i++) if (cp(i) == i){ num[i] = ++C; } for (int i=1;i<=N;i++) sz[num[cp(i)]] += A[i]; vector <EDGE> critical; for (int i=1;i<=M;i++) if (E[i].is_critical){ int a = num[cp(E[i].a)] , b = num[cp(E[i].b)]; critical.pb({a, b, E[i].c}); con[a].pb(b); con[b].pb(a); } for (int i=1;i<=K;i++) F[i].a = num[cp(F[i].a)], F[i].b = num[cp(F[i].b)]; lld ans = 0; for (int msk=1;msk<(1<<K);msk++){ for (int i=1;i<=C;i++) par[i] = i, tcon[i].clear(), tconv[i].clear(); bool is_cycle = 0; for (int i=1;i<=K;i++) if (msk & (1 << (i-1))){ int a = cp(F[i].a), b = cp(F[i].b); if (a == b){ is_cycle = 1; break; } tcon[F[i].a].pb(F[i].b); tconv[F[i].a].pb(2e9); tcon[F[i].b].pb(F[i].a); tconv[F[i].b].pb(2e9); par[b] = a; } if (is_cycle) continue; vector <EDGE> not_in_mst; for (auto &e: critical){ int a = cp(e.a), b = cp(e.b); if (a == b) not_in_mst.pb(e); else{ par[b] = a; tcon[e.a].pb(e.b); tconv[e.a].pb(0); tcon[e.b].pb(e.a); tconv[e.b].pb(0); } } H[1] = 1; dfs(1, 0); for (auto &e: not_in_mst){ int a = e.a, b = e.b; if (H[a] < H[b]) swap(a, b); while (H[a] > H[b]){ up[a] = min(up[a], e.c); a = tpar[a]; } while (a != b){ up[a] = min(up[a], e.c); up[b] = min(up[b], e.c); a = tpar[a]; b = tpar[b]; } } lld val = 0; for (int i=2;i<=C;i++) val += up[i] * subtree_sz[i]; ans = max(ans, val); } printf("%lld\n", ans); }
#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...