Submission #1189187

#TimeUsernameProblemLanguageResultExecution timeMemory
1189187juliany2Toll (APIO13_toll)C++20
16 / 100
0 ms908 KiB
#include<bits/stdc++.h> using namespace std; using ll = long long; #define all(x) (x).begin(), (x).end() struct DSU { vector<int> e; DSU(int sz) { e = vector<int>(sz + 1, -1); } int get(int x) { return e[x] < 0 ? x : e[x] = get(e[x]); } bool same_set(int a, int b) { return get(a) == get(b); } int size(int x) { return -e[get(x)]; } bool unite(int x, int y) { x = get(x), y = get(y); if (x == y) return false; if (e[x] > e[y]) swap(x, y); e[x] += e[y]; e[y] = x; return true; } }; const int N = 1e5 + 7, K = 22; int n, m, k; array<int, 2> f[N]; int p[N], head[N]; ll sz[K]; struct DSU2 { vector<int> dsu; vector<vector<int>> match; vector<int> cost; DSU2(int n) { dsu = vector<int> (n + 1); iota(all(dsu), 0); match = vector<vector<int>> (n + 1); } void add(int a, int b, int i) { match[a].push_back(i); match[b].push_back(i); cost.push_back(0); } int get(int x) { return (dsu[x] == x ? x : dsu[x] = get(dsu[x])); } int unite(int u, int v, int w) { u = get(u), v = get(v); if (u == v) return 0; int ret = 1; vector<int> &a = match[u], &b = match[v], c; while (a.size() || b.size()) { if (b.empty() || (a.size() && a.back() > b.back())) { c.push_back(a.back()); a.pop_back(); } else if (a.empty() || (b.size() && b.back() > a.back())) { c.push_back(b.back()); b.pop_back(); } else { cost[a.back()] = w; ret++; a.pop_back(); b.pop_back(); } } match[u] = c; dsu[v] = u; return ret; } }; vector<array<int, 3>> rem; vector<array<int, 2>> adj[K]; int mask[K]; ll cnt[K]; ll res = 0; void dfs(int v = 0, int p = -1) { for (auto &[u, w] : adj[v]) { if (u == p) continue; dfs(u, v); if (w == -1) { res += cnt[u] * rem[__builtin_ctz(mask[u])][2]; } mask[v] ^= mask[u]; cnt[v] += cnt[u]; } } int main() { cin.tie(0)->sync_with_stdio(false); cin >> n >> m >> k; vector<array<int, 3>> e(m); for (auto &[w, u, v] : e) cin >> u >> v >> w; DSU2 dsu(n + 1); for (int i = 0; i < k; i++) { int u, v; cin >> u >> v; f[i] = {u, v}; dsu.add(u, v, i); } for (int i = 1; i <= n; i++) cin >> p[i]; sort(all(e)); DSU comp(n + 1); for (auto &[w, u, v] : e) { int here = dsu.unite(u, v, w); if (!here) continue; if (here == 1) comp.unite(u, v); else rem.push_back({u, v, w}); } memset(head, -1, sizeof(head)); int groupcnt = 0; for (int i = 1; i <= n; i++) { if (head[comp.get(i)] == -1) head[comp.get(i)] = groupcnt++; if (head[i] == -1) head[i] = head[comp.get(i)]; } for (int i = 1; i <= n; i++) { sz[head[i]] += p[i]; } for (int i = 0; i < k; i++) { auto &[u, v] = f[i]; u = head[u], v = head[v]; } for (auto &[u, v, w] : rem) { u = head[u], v = head[v]; } ll ans = 0; for (int msk = 1; msk < (1 << k); msk++) { DSU g(k + 1); bool ok = 1; for (int i = 0; i <= k; i++) { adj[i].clear(); mask[i] = 0; cnt[i] = sz[i]; } for (int i = 0; i < k; i++) { if (msk >> i & 1) { auto &[u, v] = f[i]; if (!g.unite(u, v)) { ok = 0; break; } adj[u].push_back({v, -1}); adj[v].push_back({u, -1}); } } if (ok) { for (int i = 0; i < rem.size(); i++) { auto &[u, v, w] = rem[i]; if (g.unite(u, v)) { adj[u].push_back({v, 0}); adj[v].push_back({u, 0}); } else { mask[u] |= 1 << i; mask[v] |= 1 << i; } } res = 0; dfs(); ans = max(ans, res); } } cout << ans << '\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...