| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 114677 | WhipppedCream | Toll (APIO13_toll) | C++17 | 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>
#define pb push_back
using namespace std;
typedef vector<int> vi;
typedef long long ll;
const int maxn = 1e5+5;
const int maxk = 25;
struct edge
{
int u, v, w;
bool is_hard, in_mst;
edge(int _u, int _v, int _w)
{
u = _u; v = _v; w = _w;
is_hard = 0;
in_mst = 0;
}
bool operator < (edge other)
{
return w< other.w;
}
};
int n, m, k;
int size;
int par[maxn];
int sz[maxn];
int treecomp[maxn];
int treesz[maxn];
vi adj[maxk];
vi weight[maxk];
int dep[maxk];
int up[maxk];
int subsz[maxk];
int b4[maxk];
void setsz(int x)
{
size = x;
}
void reset()
{
for(int i = 1; i<= size; i++) par[i] = i;
}
int pong(int x)
{
if(par[x] == x) return x;
return par[x] = pong(par[x]);
}
void tfs(int u, int par)
{
subsz[u] = treesz[u];
for(int i = 0; i< (int) adj[u].size(); i++)
{
int v = adj[u][i], w = weight[u][i];
if(v == par) continue;
up[v] = w;
dep[v] = dep[u]+1;
b4[v] = u;
tfs(v, u);
subsz[u] += subsz[v];
}
}
int main()
{
scanf("%d %d %d", &n, &m, &k);
vector<edge> norm;
vector<edge> sp;
for(int i = 0; i< m; i++)
{
int u, v, w; scanf("%d %d %d", &u, &v, &w);
norm.pb(edge(u, v, w));
}
for(int i = 0; i< k; i++)
{
int u, v; scanf("%d %d", &u, &v);
sp.pb(edge(u, v, 0));
}
for(int i = 1; i<= n; i++) scanf("%d", &sz[i]);
setsz(n);
for(int i = 0; i< m; i++)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
if(a == b) continue;
par[a] = b; norm[i].in_mst = true;
}
reset();
for(int i = 0; i< k; i++)
{
int a = pong(sp[i].u), b = pong(sp[i].v);
par[a] = b;
}
for(int i = 0; i< m; i++)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
if(a == b) continue;
par[a] = b;
norm[i].is_hard = true;
}
reset();
vector<edge> soft;
for(int i = 0; i< m; i++)
{
if(norm[i].is_hard)
{
int a = pong(norm[i].u), b = pong(norm[i].v);
par[a] = b; sz[b] += sz[a];
}
else if(norm[i].in_mst) soft.pb(norm[i]);
}
int comps = 0;
for(int i = 1; i<= n; i++)
{
if(pong(i) == i)
{
comps++; treecomp[i] = comps; treesz[comps] = sz[i];
}
}
for(int i = 1; i<= n; i++)
{
if(pong(i) != i)
{
treecomp[i] = treecomp[pong[i]];
}
}
ll best = 0;
for(int mask = 0; mask < (1<<k); mask++)
{
setsz(k); reset();
bool is_cycle = false;
for(int i = 1; i<= comps; i++)
{
adj[i].clear(); weight[i].clear();
}
for(int i = 0; i< k; i++)
{
if((1<<i)&mask)
{
int a = pong(treecomp[sp[i].u]), b = pong(treecomp[sp[i].v]);
if(a == b)
{
is_cycle = true;
break;
}
par[a] = b;
adj[treecomp[sp[i].u]].pb(treecomp[sp[i].v]); weight[treecomp[sp[i].u]].pb(2e9);
adj[treecomp[sp[i].v]].pb(treecomp[sp[i].u]); weight[treecomp[sp[i].v]].pb(2e9);
}
}
if(is_cycle) continue;
vector<edges> gas;
for(int i = 0; i< (int) soft.size(); i++)
{
int a = pong(treecomp[soft[i].u]), b = pong(treecomp[soft[i].v]);
if(a == b) gas.pb(soft[i]);
else
{
par[a] = b;
adj[treecomp[soft[i].u]].pb(soft[i].v); weight[treecomp[soft[i].u]].pb(0);
adj[treecomp[soft[i].v]].pb(soft[i].u); weight[treecomp[soft[i].v]].pb( 0);
}
}
dep[treecomp[1]] = 1; tfs(treecomp[1], 0);
for(int i = 0; i< (int) gas.size(); i++)
{
int u = treecomp[gas[i].u], v = treecomp[gas[i].v];
int w = gas[i].w;
if(dep[u]< dep[v]) swap(u, v);
while(dep[u]> dep[v])
{
up[u] = min(up[u], w);
u = b4[u];
}
while(u != v)
{
up[u] = min(up[u], w);
up[v] = min(up[v], w);
u = b4[u], v = b4[v];
}
}
ll here = 0;
for(int i = 2; i<= comps; i++) here += subsz[i]*up[i];
best = max(here, best);
}
}