Submission #1221404

#TimeUsernameProblemLanguageResultExecution timeMemory
1221404Zero_OPToll (APIO13_toll)C++20
100 / 100
844 ms19924 KiB
#include <bits/stdc++.h> using namespace std; //loops (warning : long long) #define FOR(i, l, r) for(int i = (l); i < (r); ++i) #define ROF(i, r, l) for(int i = (r - 1); i >= l; --i) #define rep(i, l, r) for(int i = (l); i < (r); ++i) //pairs, tuples #define mp make_pair #define mt make_tuple #define ff first #define ss second //vectors #define all(v) begin(v), end(v) #define rall(v) rbegin(v), rend(v) #define pb push_back #define eb emplace_back #define sum_of(v) accumulate(all(v), 0ll) #define sz(v) (int)v.size() #define compact(v) v.erase(unique(all(v)), end(v)) //binary search #define lwb lower_bound #define upb upper_bound //other stuffs #define dbg(x) "[" #x " = " << (x) << "]" #define file(task) if(fopen(task".inp", "r")){ freopen(task".inp", "r", stdin); freopen(task".out", "w", stdout); } template<typename T> bool minimize(T& a, const T& b){ if(a > b) return a = b, true; return false; } template<typename T> bool maximize(T& a, const T& b){ if(a < b) return a = b, true; return false; } using ll = long long; using ull = unsigned long long; using ld = long double; using db = double; using pi = pair<int, int>; using pl = pair<ll, ll>; using vi = vector<int>; using vb = vector<bool>; using vl = vector<ll>; using vpi = vector<pi>; using vpl = vector<pl>; mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count()); const int MAX = 3e5 + 5; struct edge{ int u, v, w; edge(int u, int v, int w) : u(u), v(v), w(w) {} edge() : u(0), v(0), w(0) {} bool operator < (const edge& o) const { return w < o.w; } } e[MAX], add[20], mst[MAX]; struct DSU{ vi lab; int components; DSU(int n) : lab(n, -1), components(n) {} int root(int u){ return lab[u] < 0 ? u : (lab[u] = root(lab[u])); } bool join(int u, int v){ u = root(u); v = root(v); if(u == v) return false; if(lab[u] > lab[v]) swap(u, v); --components; lab[u] += lab[v]; lab[v] = u; return true; } void reset(){ fill(all(lab), -1); components = sz(lab); } }; int N, M, K, p[MAX], c[MAX]; int avail[30], par[30], depth[30]; ll sum_p[30], sum[30]; bool type[MAX]; vi adj[MAX]; void dfs_cc(int u, int color){ c[u] = color; for(auto v : adj[u]) if(c[v] == -1){ // cout << "mst : " << u+1 << ' ' << v+1 << '\n'; dfs_cc(v, color); } } void dfs_tree(int u, int p){ // cout << "visit : " << u << '\n'; sum[u] = sum_p[u]; for(auto v : adj[u]) if(v != p){ // cout << dbg(u) << dbg(v) << '\n'; depth[v] = depth[u] + 1; par[v] = u; dfs_tree(v, u); sum[u] += sum[v]; } } void update(int u, int v, int w){ // cout << "update : " << u << ' ' << v << ' ' << w << '\n'; if(depth[u] < depth[v]) swap(u, v); while(depth[u] > depth[v]){ minimize(avail[u], w); u = par[u]; } while(u != v){ minimize(avail[u], w); u = par[u]; minimize(avail[v], w); v = par[v]; } } void testcase(int ntestcase){ cin >> N >> M >> K; rep(i, 0, M){ int u, v, w; cin >> u >> v >> w; --u, --v; e[i] = edge(u, v, w); } rep(i, 0, K){ int u, v; cin >> u >> v; --u, --v; add[i] = edge(u, v, 0); } rep(i, 0, N) cin >> p[i]; sort(e, e + M); DSU dsu(N); rep(i, 0, K){ dsu.join(add[i].u, add[i].v); } rep(i, 0, M){ type[i] = dsu.join(e[i].u, e[i].v); if(type[i]){ adj[e[i].u].pb(e[i].v); adj[e[i].v].pb(e[i].u); } } dsu.reset(); rep(i, 0, M){ if(type[i] == 1) dsu.join(e[i].u, e[i].v); } vector<edge> extra; rep(i, 0, M){ if(type[i] == 0){ if(dsu.join(e[i].u, e[i].v)){ extra.eb(e[i]); } } } memset(c, -1, sizeof(c)); int cnt = 0; rep(i, 0, N){ if(c[i] == -1){ dfs_cc(i, cnt++); } sum_p[c[i]] += p[i]; } // rep(i, 0, cnt) cout << sum_p[i] << ' '; cout << '\n'; rep(i, 0, sz(extra)) extra[i].u = c[extra[i].u], extra[i].v = c[extra[i].v]; rep(i, 0, K) add[i].u = c[add[i].u], add[i].v = c[add[i].v]; // for(auto [u, v, w] : extra) cout << "extra : " << u << ' ' << v << ' ' << w << '\n'; ll ans = 0; DSU compressed_dsu(cnt); rep(mask, 1, (1 << K)){ compressed_dsu.reset(); rep(i, 0, cnt) avail[i] = 1e9, adj[i].clear(); bool ok = true; rep(i, 0, K) if(mask >> i & 1){ if(!compressed_dsu.join(add[i].u, add[i].v)){ ok = false; break; } adj[add[i].u].pb(add[i].v); adj[add[i].v].pb(add[i].u); } if(!ok) continue; rep(i, 0, sz(extra)){ type[i] = (compressed_dsu.join(extra[i].u, extra[i].v)); if(type[i]){ adj[extra[i].u].pb(extra[i].v); adj[extra[i].v].pb(extra[i].u); } } // assert(compressed_dsu.components == 1); dfs_tree(0, -1); rep(i, 0, sz(extra)){ update(extra[i].u, extra[i].v, extra[i].w); } ll cur = 0; rep(i, 0, K) if(mask >> i & 1){ int lower = (depth[add[i].u] < depth[add[i].v] ? add[i].v : add[i].u); cur += 1LL * sum[lower] * avail[lower]; // cout << dbg(sum[lower]) << dbg(avail[lower]) << '\n'; } // cout << bitset<3>(mask) << " : " << cur << '\n'; maximize(ans, cur); // cout << "____________________\n"; } cout << ans << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("task.inp", "r", stdin); freopen("task.out", "w", stdout); #endif // LOCAL int T = 1; // cin >> T; FOR(i, 0, T) testcase(i); return 0; } /* 9 14 5 1 6 9 5 3 20 5 6 18 7 3 9 2 6 18 9 1 20 4 1 20 5 1 14 8 1 7 3 2 8 2 8 19 2 7 12 5 1 18 5 9 8 5 7 5 3 9 1 9 3 2 9 10 18 12 15 2 8 5 9 17 1386 */
#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...