제출 #446519

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
446519		Nima_Naderi	Toll (APIO13_toll)	C++14	16 / 100	6 ms	7372 KiB

toll

//In the name of God
//#pragma GCC optimize("O2")
#include<bits/stdc++.h>
#define Mp make_pair
using namespace std;

typedef long long ll;
typedef pair<ll, ll> pll;
const ll MXN = 3e5 + 10;
ll n, m, k;
ll A[MXN], from[MXN], to[MXN], W[MXN];
ll Par[MXN], Sz[MXN];
vector<pair<ll, pll>> E;
vector<pll> adj[MXN];
ll Find(ll x){
	return (Par[x] == x ? x : Par[x] = Find(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];
	return 1;
}
inline void add_edge(ll u, ll v, ll w){
	adj[u].push_back(Mp(v, w));
	adj[v].push_back(Mp(u, w));
}
ll now;
void dfs(ll u, ll par, ll dis){
	now += dis * A[u];
	for(auto Pr : adj[u]){
		ll v, w; tie(v, w) = Pr;
		if(v == par) continue;
		dfs(v, u, dis + w);
	}
}
int main(){
	ios::sync_with_stdio(0);cin.tie(0); cout.tie(0);
	cin >> n >> m >> k;
	iota(Par, Par + n + 1, 0), fill(Sz, Sz + n + 1, 1);
	for(int i = 1; i <= m; i ++){
		ll u, v, w; cin >> u >> v >> w;
		E.push_back(Mp(w, Mp(u, v)));
	}
	sort(E.begin(), E.end());
	for(int i = 0; i < k; i ++){
		ll u, v; cin >> u >> v;
		from[i] = u, to[i] = v;
	}
	for(int i = 1; i <= n; i ++) cin >> A[i];
	for(auto e : E){
		ll w = e.first, u, v; tie(u, v) = e.second;
		ll ru = Find(u), rv = Find(v);
		if(ru == rv) continue;
		if(ru > rv) swap(ru, rv);
		for(int i = 0; i < k; i ++){
			ll mu = Find(from[i]), mv = Find(to[i]);
			if(mu > mv) swap(mu, mv);
			if(mu == ru && mv == rv) W[i] = w;
		}
		Union(ru, rv);
	}
	ll ans = -1e18, base;
	for(int mask = 0; mask < (1LL << k); mask ++){
		iota(Par, Par + n + 1, 0), fill(Sz, Sz + n + 1, 1);
		for(int i = 1; i <= n; i ++) adj[i].clear();
		for(int i = 0; i < k; i ++){
			if((mask >> i) & 1LL){
				if(Union(from[i], to[i])) add_edge(from[i], to[i], W[i]);
			}
		}
		for(auto e : E){
			ll w = e.first, u, v; tie(u, v) = e.second;
			if(Union(u, v)) add_edge(u, v, 0);
		}
		/*
		cout << "halat : \n";
		for(int i = 1; i <= n; i ++){
			for(auto Pr : adj[i]) cout << Pr.first << ' ';
			cout << '\n';
		}
		*/
		now = 0, dfs(1, 0, 0);
		if(!mask) base = now;
		//cout << now << '\n';
		ans = max(ans, now);
	}
	cout << ans << '\n';
	return 0;
}
// Nima 

컴파일 시 표준 에러 (stderr) 메시지

toll.cpp: In function 'int main()':
toll.cpp:74:7: warning: unused variable 'w' [-Wunused-variable]
   74 |    ll w = e.first, u, v; tie(u, v) = e.second;
      |       ^
toll.cpp:64:18: warning: variable 'base' set but not used [-Wunused-but-set-variable]
   64 |  ll ans = -1e18, base;
      |                  ^~~~

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