Submission #1188800

#TimeUsernameProblemLanguageResultExecution timeMemory
1188800juliany2Toll (APIO13_toll)C++20
16 / 100
140 ms229376 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; int n, m, k; int dsu[N]; set<int> match[N]; array<int, 3> f[N]; int p[N], head[N]; ll sz[N]; vector<array<int, 2>> adj[N]; 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; if (match[u].size() < match[v].size()) match[u].swap(match[v]); int ret = 1; for (int x : match[v]) { if (match[u].count(x)) { match[u].erase(x); f[x][2] = w; ret = -1; } else match[u].insert(x); } dsu[v] = u; return ret; } ll dfs(int v = 0, int p = -1, ll sum = 0) { ll val = sum * sz[v]; for (auto &[u, w] : adj[v]) { if (u != p) { val += dfs(u, v, sum + w); } } return val; } 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; for (int i = 0; i < k; i++) { int u, v; cin >> u >> v; f[i] = {u, v}; match[u].insert(i); match[v].insert(i); } for (int i = 1; i <= n; i++) cin >> p[i]; sort(all(e)); for (int i = 1; i <= n; i++) dsu[i] = i; DSU comp(n + 1); vector<array<int, 3>> rem; for (auto &[w, u, v] : e) { int here = 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]; } vector<bool> used(1e6 + 7); ll ans = 0; for (int msk = 1; msk < (1 << k); msk++) { bool ok = 1; for (int i = 0; i < k; i++) { if (msk >> i & 1) { auto &[u, v, w] = f[i]; if (used[w]) { ok = 0; break; } used[w] = 1; u = head[u], v = head[v]; adj[u].push_back({v, w}); adj[v].push_back({u, w}); } } for (auto &[u, v, w] : rem) { if (!used[w]) { u = head[u], v = head[v]; adj[u].push_back({v, 0}); adj[v].push_back({u, 0}); } } ans = max(ans, dfs()); for (int i = 0; i <= k; i++) { used[f[i][2]] = 0; adj[i].clear(); } } 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...