Submission #1221397

#TimeUsernameProblemLanguageResultExecution timeMemory
1221397Zero_OPToll (APIO13_toll)C++20
16 / 100
7 ms15688 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, used; DSU(int n) : lab(n, -1), used() {} 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); if(lab[u] == -1) used.pb(u); if(lab[v] == -1) used.pb(v); lab[u] += lab[v]; lab[v] = u; return true; } void reset(){ for(auto u : used) lab[u] = -1; used.clear(); } }; 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){ dfs_cc(v, color); } } void dfs_tree(int u, int p){ sum[u] = sum_p[u]; for(auto v : adj[u]) if(v != p){ depth[v] = depth[u] + 1; par[v] = u; dfs_tree(v, u); sum[u] += sum[v]; } } void update(int u, int v, int w){ 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, 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]; 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)); } dfs_tree(0, -1); rep(i, 0, sz(extra)){ if(!type[i]) 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]; } maximize(ans, cur); } cout << ans << '\n'; } int main(){ ios_base::sync_with_stdio(0); cin.tie(0); #ifdef LOCAL freopen("task.inp", "r", stdin); #endif // LOCAL int T = 1; // cin >> T; FOR(i, 0, T) testcase(i); 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...