Submission #466326

#	Time	Username	Problem	Language	Result	Execution time	Memory
466326		Nima_Naderi	Toll (APIO13_toll)	C++14	100 / 100	2293 ms	49848 KiB

toll

//In the name of God
#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
typedef tuple<ll, ll, ll> tpl;
const ll MXN = 3e5 + 10;
ll n, m, k, ts, te, ans;
ll A[MXN], B[MXN], mp[MXN];
ll U[MXN], V[MXN], W[MXN];
ll Um[MXN], Vm[MXN], Wm[MXN];
ll Sz[MXN], Par[MXN], sz[MXN], par[MXN];
vector<tpl> Edge, E, Other;
vector<ll> adj[MXN];
inline void add_edge(ll u, ll v, ll w){
	U[++ te] = u, V[te] = v, W[te] = w;
	adj[u].push_back(te), adj[v].push_back(te);
}
ll Find(ll x){
	return (Par[x] == x ? x : Par[x] = Find(Par[x]));
}
ll Find0(ll x){
	return (par[x] == x ? x : par[x] = Find0(par[x]));
}
bool Union(ll x, ll y){
	x = Find(x), y = Find(y);
	if(x == y) return 0;
	if(Sz[x] < Sz[y]) swap(x, y);
	Par[y] = x, Sz[x] += Sz[y];
	B[x] += B[y];
	return 1;
}
bool Union0(ll x, ll y){
	x = Find0(x), y = Find0(y);
	if(x == y) return 0;
	if(sz[x] < sz[y]) swap(x, y);
	par[y] = x, sz[x] += sz[y];
	return 1;
}
ll timer;
ll Stm[MXN], Ftm[MXN], idp[MXN];
void dfs(ll u){
	Stm[u] = ++ timer;
	for(auto id : adj[u]){
		ll v = U[id] ^ V[id] ^ u;
		if(id != idp[u]) idp[v] = id, dfs(v);
	}
	Ftm[u] = timer;
}
inline bool Is_Jad(ll j, ll u){
	return Stm[j] <= Stm[u] && Ftm[u] <= Ftm[j];
}
ll sub[MXN];
vector<pair<ll, ll>> G[MXN];
ll DFS(ll u, ll par){
	ll res = 0; sub[u] = A[u];
	for(auto Pr : G[u]){
		ll v, w; tie(v, w) = Pr;
		if(v != par) res += DFS(v, u) + sub[v] * w, sub[u] += sub[v];
	}
	return res;
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	iota(par, par + MXN, 0), fill(sz, sz + MXN, 1);
	iota(Par, Par + MXN, 0), fill(Sz, Sz + MXN, 1);
	for(int i = 1; i <= m; i ++){
		ll u, v, w; cin >> u >> v >> w;
		Edge.push_back({w, u, v});
	}
	for(int i = 1; i <= k; i ++){
		ll u, v; cin >> u >> v;
		Um[i] = u, Vm[i] = v;
		Union0(u, v);
	}
	for(int i = 1; i <= n; i ++) cin >> B[i];
	sort(Edge.begin(), Edge.end());
	for(auto Tp : Edge){
		ll w, u, v; tie(w, u, v) = Tp;
		if(Union0(u, v)) Union(u, v);
		else E.push_back({w, u, v});
	}
	for(int i = 1; i <= n; i ++){
		ll v = Find(i);
		if(!mp[v]){
			mp[v] = ++ ts;
			A[ts] = B[v];
		}
		mp[i] = mp[v];
	}
	
	//cout << "MAP : ";
	//for(int i = 1; i <= n; i ++) cout << i << "-> " << mp[i] << '\n';

	iota(par, par + ts + 1, 0), fill(sz, sz + ts + 1, 1);
	for(auto Tp : E){
		ll w, u, v; tie(w, u, v) = Tp;
		u = mp[u], v = mp[v];
		if(Union0(u, v)) Other.push_back({u, v, w});
	}
	for(int i = 1; i <= k; i ++) Um[i] = mp[Um[i]], Vm[i] = mp[Vm[i]];
	for(int mask = 1; mask < (1LL << k); mask ++){
		bool brk = false; te = timer = 0;
		for(int i = 1; i <= ts; i ++) adj[i].clear(), G[i].clear(), par[i] = i, sz[i] = 1;
		for(int b = 0; b < k; b ++){
			if(((mask >> b) & 1LL) == 0) continue;
			ll i = b + 1;
			if(!Union0(Um[i], Vm[i])){
				brk = true; break;
			}
			add_edge(Um[i], Vm[i], 1e9);
			
			//cout << Um[i] << ' ' << Vm[i] << '\n';
		}
		if(brk) continue;
		for(auto Tp : Other){
			ll u, v, w; tie(u, v, w) = Tp;
			if(Union0(u, v)) add_edge(u, v, 0);
		}
		assert(te == ts - 1);
		dfs(1);
		for(auto Tp : Other){
			ll u, v, w; tie(u, v, w) = Tp;
			while(!Is_Jad(u, v)){
				W[idp[u]] = min(W[idp[u]], w);
				u = U[idp[u]] ^ V[idp[u]] ^ u;
			}
			while(v != u){
				W[idp[v]] = min(W[idp[v]], w);
				v = U[idp[v]] ^ V[idp[v]] ^ v;
			}
		}
		for(int i = 1; i <= te; i ++){
			G[U[i]].push_back({V[i], W[i]});
			G[V[i]].push_back({U[i], W[i]});
		}
		ans = max(ans, DFS(mp[1], 0));
		if(0 && ans == 19){
			cout << mask << '\n';
			for(int i = 1; i <= te; i ++){
				cout << U[i] << ' ' << V[i] << "  W : " << W[i] << '\n';
			}
			return 0;
		}
	//	cout << '\n';
	}
	cout << ans << '\n';
	return 0;
}
// N.N
// Strom

• Subtask 1: 16 / 16
• Subtask 2: 18 / 18
• Subtask 3: 22 / 22
• Subtask 4: 22 / 22
• Subtask 5: 22 / 22