Submission #1235119

#TimeUsernameProblemLanguageResultExecution timeMemory
1235119hahahoang132Toll (APIO13_toll)C++20
56 / 100
438 ms67740 KiB
#include<bits/stdc++.h> using namespace std; #define ll long long const ll N = 5e5 + 5; const ll mod = 1e9 + 7; const ll inf = LLONG_MAX/5; #define bit(x,y) ((x >> y) & 1) typedef struct { ll u,v,w; }burh; ll cmp(burh x,burh y) { return x.w < y.w; } burh p[N]; burh kp[N]; bool seen[N]; ll par[N],w[N],mst[N],np[1005],nw[1005],limit[1005],sw[1005],parr[1005]; burh sus[1005]; vector<pair<ll,ll>> a[N]; vector<ll> b[N]; vector<ll> g[N]; ll n,m,n2,m2,k; ll h[N]; void build(ll x, ll px) { sw[x] = nw[x]; for(auto y : g[x]) { if(y == px) continue; parr[y] = x; h[y] = h[x] + 1; build(y,x); sw[x] += sw[y]; } } void setlimit(ll x, ll y, ll z) { if(h[x] < h[y]) swap(x,y); while(h[x] > h[y]) { limit[x] = min(limit[x],z); x = parr[x]; } while(x != y) { limit[x] = min(limit[x],z); limit[y] = min(limit[y],z); x = parr[x]; y = parr[y]; } } ll fp(ll x) { if(par[x] == 0) return x; else { par[x] = fp(par[x]); return par[x]; } } void hop(ll x, ll y) { ll px = fp(x); ll py = fp(y); if(px == py) return; par[px] = py; } int main() { ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m >> k; ll i,j; for(i = 1;i <= m;i++) { cin >> p[i].u >> p[i].v >> p[i].w; a[p[i].u].push_back({p[i].v,i}); a[p[i].v].push_back({p[i].u,i}); } for(i = 1;i <= k;i++) { cin >> kp[i].u >> kp[i].v; b[kp[i].u].push_back(kp[i].v); b[kp[i].v].push_back(kp[i].u); } for(i = 1;i <= n;i++) cin >> w[i]; priority_queue<pair<ll,pair<ll,ll>>,vector<pair<ll,pair<ll,ll>>>,greater<pair<ll,pair<ll,ll>>>> pq; pq.push({0,{1,0}}); while(!pq.empty()) { ll x = pq.top().second.first; ll ip = pq.top().second.second; pq.pop(); if(seen[x] == 1) continue; seen[x] = 1; mst[ip] = 1; for(auto tmp : a[x]) { ll y = tmp.first; ll id = tmp.second; ll dis = p[id].w; if(seen[y] == 1) continue; pq.push({dis,{y,id}}); } } for(i = 1;i <= n;i++) seen[i] = 0; pq.push({0,{1,0}}); while(!pq.empty()) { ll x = pq.top().second.first; ll ip = pq.top().second.second; pq.pop(); if(seen[x] == 1) continue; seen[x] = 1; mst[ip]++; for(auto tmp : a[x]) { ll y = tmp.first; ll id = tmp.second; ll dis = p[id].w; if(seen[y] == 1) continue; pq.push({dis,{y,id}}); } for(auto y : b[x]) { if(seen[y] == 1) continue; pq.push({0,{y,0}}); } } for(i = 1;i <= m;i++) { if(mst[i] == 2) { hop(p[i].u,p[i].v); } } for(i = 1;i <= n;i++) { if(np[fp(i)] == 0) { np[fp(i)] = ++n2; } np[i] = np[fp(i)]; nw[np[i]] += w[i]; } for(i = 1;i <= n;i++) par[i] = 0; for(i = 1;i <= k;i++) { kp[i].u = np[kp[i].u]; kp[i].v = np[kp[i].v]; } for(i = 1;i <= m;i++) { if(mst[i] == 1) { if(np[p[i].u] != np[p[i].v]) { sus[++m2] = {np[p[i].u],np[p[i].v],p[i].w}; } } } sort(sus + 1,sus + 1 + m2,cmp); ll tans = 0; for(i = 0;i < (1 << k);i++) { for(j = 1;j <= n2;j++) { par[j] = 0; g[j].clear(); } ll flag = 0; for(j = 1;j <= k;j++) { if(bit(i,j - 1)) { if(fp(kp[j].u) == fp(kp[j].v)) { flag = 1; break; }else { hop(kp[j].u,kp[j].v); g[kp[j].u].push_back(kp[j].v); g[kp[j].v].push_back(kp[j].u); } } } if(flag == 1) continue; for(j = 1;j <= m2;j++) { if(fp(sus[j].u) != fp(sus[j].v)) { hop(sus[j].u,sus[j].v); g[sus[j].u].push_back(sus[j].v); g[sus[j].v].push_back(sus[j].u); } } h[1] = 1; build(1,0); for(j = 1;j <= n2;j++) { limit[j] = inf; } for(j = 1;j <= m2;j++) { setlimit(sus[j].u,sus[j].v,sus[j].w); } ll ans = 0; for(j = 1;j <= k;j++) { if(bit(i,j - 1)) { if(h[kp[j].u] < h[kp[j].v]) swap(kp[j].u,kp[j].v); ll x = kp[j].u; ans += limit[x] * sw[x]; } } tans = max(tans,ans); } cout << tans; }
#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...