| # | Time | Username | Problem | Language | Result | Execution time | Memory |
|---|---|---|---|---|---|---|---|
| 441680 | AriaH | 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.
/** work as hard as you can and keep the first place **/
#pragma GCC optimize("O2")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair < int, int > pii;
typedef pair < ll, ll > pll;
#define F first
#define S second
#define all(x) x.begin(), x.end()
#define SZ(x) (int)x.size()
#define Mp make_pair
const int N = 3e5 + 50;
const ll mod = 1e9 + 7;
const ll inf = 8e18;
const int LOG = 20;
ll pw(ll a, ll b, ll M = mod, ll ret = 1) { while(b) { ret = ret * (b & 1? a : 1) % M, a = a * a % M, b >>= 1; } return ret; }
ll tot, ret, ted[N], sub[N], size[N];
int n, m, k, ptr, ROOT, V[N], U[N], C[N], par[N], ord[N], in1[N], in2[N], T[N], query[N], St[N], Fi[N];
vector < int > vec, roots, G[N];
inline void init() { for(int i = 1; i <= n; i ++) par[i] = i, ted[i] = T[i]; }
int get(int x) { return (x == par[x]? x : par[x] = get(par[x])); }
bool unify(int v, int u)
{
v = get(v), u = get(u);
if(v == u) return 0;
par[u] = v;
ted[v] += ted[u];
return 1;
}
bool cmp(int i, int j)
{
return C[i] < C[j];
}
set < pii > st[N];
void pre(int v, int last = 0)
{
St[v] = ++ptr;
for(auto id : G[v])
{
if(id == last) continue;
int u = V[id] ^ U[id] ^ v;
pre(u, id);
}
Fi[v] = ptr;
///printf("v = %d St = %d Fi = %d\n", v, St[v], Fi[v]);
}
void dfs(int v, int last = 0)
{
sub[v] = size[v];
for(auto id : G[v])
{
if(id == last) continue;
int u = V[id] ^ U[id] ^ v;
dfs(u, id);
if(SZ(st[v]) < SZ(st[u])) st[v].swap(st[u]);
for(auto now : st[u])
{
int node = now.S;
if(!(St[v] <= St[node] && Fi[node] <= Fi[v]))
{
st[v].insert(now);
}
}
sub[v] += sub[u];
}
pii cu = *st[v].begin();
while(St[v] <= St[cu.S] && Fi[cu.S] <= Fi[v])
{
st[v].erase(cu);
cu = *st[v].begin();
}
if(last > m)
{
ret += cu.F * sub[v];
}
}
void solve(int mask)
{
///printf("mask = %d\n", mask);
ptr = 0;
ret = 0;
for(auto v : roots) G[v].clear(), par[v] = v, ted[v] = 0, st[v].clear();
for(int i = m + 1; i <= m + k; i ++)
{
int id = i - m - 1;
if(mask >> id & 1)
{
G[V[i]].push_back(i);
G[U[i]].push_back(i);
///printf("E = %d\n", i);
if(!unify(V[i], U[i])) return;
}
}
for(auto i : vec)
{
if(unify(V[i], U[i]))
{
G[V[i]].push_back(i);
G[U[i]].push_back(i);
///printf("E = %d\n", i);
}
else
{
st[V[i]].insert({C[i], U[i]});
st[U[i]].insert({C[i], V[i]});
}
}
pre(ROOT);
dfs(ROOT);
tot = max(tot, ret);
}
int main()
{
scanf("%d%d%d", &n, &m, &k);
for(int i = 1; i <= m; i ++)
{
scanf("%d%d%d", &V[i], &U[i], &C[i]);
ord[i] = i;
}
sort(ord + 1, ord + m + 1, cmp);
init();
for(int j = 1; j <= m; j ++)
{
int i = ord[j];
in1[i] = unify(V[i], U[i]);
}
init();
for(int i = m + 1; i <= m + k; i ++)
{
scanf("%d%d", &V[i], &U[i]);
unify(V[i], U[i]);
}
for(int i = 1; i <= n; i ++) { scanf("%d", &T[i]); }
for(int j = 1; j <= m; j ++)
{
int i = ord[j];
in2[i] = unify(V[i], U[i]);
}
init();
for(int i = 1; i <= m; i ++)
{
if(in1[i] > in2[i])
{
vec.push_back(i);
}
if(in2[i])
{
unify(V[i], U[i]);
}
}
for(int i = 1; i <= n; i ++)
{
roots.push_back(get(i));
}
sort(all(roots));
roots.resize(unique(all(roots)) - roots.begin());
for(auto v : roots)
{
size[v] = ted[v];
}
for(int i = 1; i <= m + k; i ++)
{
V[i] = get(V[i]), U[i] = get(U[i]);
}
ROOT = get(1);
for(int mask = 0; mask < 1 << k; mask ++)
{
solve(mask);
}
printf("%lld\n", tot);
return 0;
}
/** test corner cases(n = 1?) watch for overflow or minus indices **/