oj.uz

Submission #466326

# Submission time Handle Problem Language Result Execution time Memory
466326 2021-08-18T16:00:13 Z Nima_Naderi Toll (APIO13_toll) C++14
100 / 100
 2293 ms 49848 KB 
//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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 14 ms 23868 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 14 ms 23868 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 16 ms 24204 KB Output is correct
6 Correct 16 ms 24204 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 14 ms 23868 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 16 ms 24204 KB Output is correct
6 Correct 16 ms 24204 KB Output is correct
7 Correct 212 ms 49788 KB Output is correct
8 Correct 228 ms 49816 KB Output is correct
9 Correct 224 ms 49820 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 23884 KB Output is correct
2 Correct 12 ms 23800 KB Output is correct
3 Correct 14 ms 23868 KB Output is correct
4 Correct 14 ms 23884 KB Output is correct
5 Correct 16 ms 24204 KB Output is correct
6 Correct 16 ms 24204 KB Output is correct
7 Correct 212 ms 49788 KB Output is correct
8 Correct 228 ms 49816 KB Output is correct
9 Correct 224 ms 49820 KB Output is correct
10 Correct 1623 ms 49816 KB Output is correct
11 Correct 2274 ms 49840 KB Output is correct
12 Correct 2293 ms 49848 KB Output is correct