| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 739110 | damwuan | Toll (APIO13_toll) | C++14 | 0 ms | 0 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include<bits/stdc++.h>
using namespace std;
#define task "test"
#define pb push_back
#define fi first
#define se second
#define bit(n,i) ((n>>i)&1)
#define all(x) x.begin(),x.end()
//#pragma GCC optimize("O2,unroll-loops")
//#pragma GCC target("avx,avx2,bmi,bmi2,sse,sse2,sse3,ssse3,sse4,popcnt")
#define int long long
typedef long long ll;
typedef pair<int,int> pii;
typedef double ld;
typedef pair<ld,ld> pdd;
typedef pair<ll,ll> pll;
const ll maxn=3e5+69;
const ll inf=1e18;
const ll mod=1e9+7;
const ll base = 223;
int n, m, k;
int id[30], Cnt;
int dd[maxn];
struct Edge
{
int u, v, w;
bool operator < (const Edge& o) const
{
return w < o.w;
}
}e[maxn];
struct usd
{
int par[maxn];
void init(int x=n) {fill(par,par+1+x,-1);}
int Find(int u)
{
return par[u] < 0 ? u : par[u] = Find(par[u]);
}
bool Union(int u, int v)
{
if ((u = Find(u)) == (v = Find(v))) return false;
if (par[u] > par[v]) swap(u,v);
par[u] += par[v];
par[v] = u;
return true;
}
}dsu;
vector<pii> adj[30];
vector<int> used, tocheck;
int ans, res,sum[30], dep[30], up[30], a[maxn] , sm[30];
bool spe[30];
void dfs(int u,int pre)
{
dep[u]=dep[pre]+1;
up[u] = pre;
sm[u]=sum[u];
for (auto x: adj[u])
{
int v=x.fi;
int w=x.se;
if (v==pre) continue;
dfs(v,u);
sm[u]+=sm[v];
if (w <= -inf) spe[v]=1;
}
}
void lca(int u,int v,int w)
{
if (dep[u] < dep[v]) swap(u,v);
while (dep[u] > dep[v])
{
if (spe[u])
{
res+=sm[u]*w;
//spe[u]=0;
}
sm[u]=0
u=up[u];
}
while (u!=v)
{
if (spe[u])
{
res+=sm[u]*w;
//spe[u]=0;
}
if (spe[v])
{
res+=sm[v]*w;
//spe[v]=0;
}
sm[u]=sm[v]=0;
u=up[u];
v=up[v];
}
}
int cal(int mask)
{
res=0;
tocheck.clear();
for (int i = 1; i <= Cnt;i++)
{
adj[i].clear();
spe[i]=0;
dep[i]=0;
}
dsu.init(Cnt);
for (int i=1;i<=k;i++)
{
if ((mask>>(i-1))&1)
{
if (dsu.Union(e[i].u,e[i].v))
{
adj[e[i].u].pb({e[i].v, -inf});
adj[e[i].v].pb({e[i].u, -inf});
}
}
}
for (int i: used)
{
int u=e[i].u;
int v=e[i].v;
int w=e[i].w;
if (dsu.Union(u, v))
{
adj[u].pb({v,w});
adj[v].pb({u,w});
}
else tocheck.pb(i);
}
dfs(1,1);
for (int i: tocheck) lca(e[i].u, e[i].v, e[i].w);
return res;
}
void sol()
{
cin >> n >> m >> k;
for (int i = 1;i <= m ;i++)
{
cin >> e[i].u >> e[i].v >> e[i].w;
}
for (int i = m+1;i <= m+k;i++)
{
cin >> e[i].u >> e[i].v;
e[i].w=-inf;
}
for (int i = 1;i <= n; i++)
{
cin >> a[i];
}
sort(e + 1, e + 1 + m + k);
dsu.init();
for (int i = 1; i <= k ; i++)
{
dsu.Union(e[i].u, e[i].v);
}
for (int i = k+1; i <= m+k; i++)
{
if (dsu.Union(e[i].u,e[i].v))
{
used.pb(i);
}
}
dsu.init();
for (int i: used) dsu.Union(e[i].u, e[i].v);
for (int i = 1;i <= n ;i++)
{
int x = dsu.Find(i);
if (!dd[x]) dd[x]=++Cnt;
id[i] = dd[x];
sum[dd[x]]+=a[i];
}
for (int i = 1;i <= m+k; i++)
{
e[i].u = id[e[i].u];
e[i].v = id[e[i].v];
}
used.clear();
dsu.init(Cnt);
// for (int i = 1 ;i <= k; i++)
// {
// Union(e[i].u,e[i].v);
// }
for (int i = k + 1 ;i <= k+m; i++)
{
if(dsu.Union(e[i].u, e[i].v))
{
used.pb(i);
}
}
for (int mask = 1; mask < (1<<k) ; mask++)
{
ans= max(ans,cal(mask));
}
cout << ans;
}
int32_t main()
{
ios_base::sync_with_stdio(false);
cin.tie(NULL);
if (fopen(task".inp","r"))
{
freopen(task".inp","r",stdin);
freopen(task".out","w",stdout);
}
int t=1;//cin >> t;
while (t--)
{
sol();
}
}
/*
5 5 1
3 5 2
1 2 3
2 3 5
2 4 4
4 3 6
1 3
10 20 30 40 50
*/