oj.uz

답안 #466321

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
466321 2021-08-18T15:03:24 Z Nima_Naderi 통행료 (APIO13_toll) C++14
16 / 100
 13 ms 23884 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;
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];
	}
	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)) add_edge(u, v, w);
	}
	dfs(1);
	for(int i = 1; i <= k; i ++){
		ll u = (Um[i] = mp[Um[i]]), v = (Vm[i] = mp[Vm[i]]);
		while(!Is_Jad(u, v)){
			Wm[i] = max(Wm[i], W[idp[u]]);
			u = U[idp[u]] ^ V[idp[u]] ^ u;
		}
		while(v != u){
			Wm[i] = max(Wm[i], W[idp[v]]);
			v = U[idp[v]] ^ V[idp[v]] ^ v;
		}
	}
	assert(te == ts - 1);
	for(int mask = 1; mask < (1LL << k); mask ++){
		bool brk = false;
		for(int i = 1; i <= ts; i ++) G[i].clear(), par[i] = i, sz[i] = 1;
		for(int b = 0; b < k; b ++){
			if(((mask >> b) & 1LL) == 0) continue;
			int i = b + 1;
			G[Um[i]].push_back({Vm[i], Wm[i]});
			G[Vm[i]].push_back({Um[i], Wm[i]});
			if(!Union0(Um[i], Vm[i])){
				brk = true; break;
			}
		}
		if(brk) continue;
		for(int i = 1; i < ts; i ++){
			if(Union0(U[i], V[i])){
				G[U[i]].push_back({V[i], 0});
				G[V[i]].push_back({U[i], 0});
			}
		}
		ans = max(ans, DFS(mp[1], 0));
	}
	cout << ans << '\n';
	return 0;
}
// N.N
// Strom

Subtask #1
16.0 / 16.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct

Subtask #2
0 / 18.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Incorrect 13 ms 23812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Incorrect 13 ms 23812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Incorrect 13 ms 23812 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# 결과 실행 시간 메모리 Grader output
1 Correct 13 ms 23884 KB Output is correct
2 Correct 12 ms 23844 KB Output is correct
3 Incorrect 13 ms 23812 KB Output isn't correct
4 Halted 0 ms 0 KB -