oj.uz

Submission #446520

# Submission time Handle Problem Language Result Execution time Memory
446520 2021-07-22T09:33:11 Z Nima_Naderi Toll (APIO13_toll) C++14
16 / 100
 6 ms 7392 KB 
//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, E2;
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();
		E2.clear();
		for(int i = 0; i < k; i ++){
			if((mask >> i) & 1LL){
				E2.push_back(Mp(W[i], Mp(from[i], to[i])));
			}
		}
		sort(E2.begin(), E2.end());
		for(auto e : E2){
			ll w = e.first, u, v; tie(u, v) = e.second;
			if(Union(u, v)) add_edge(u, v, w);
		}
		for(auto e : E){
			ll w = e.first, u, v; tie(u, v) = e.second;
			if(Union(u, v)) add_edge(u, v, 0);
		}
		now = 0, dfs(1, 0, 0);
		if(!mask) base = now;
		ans = max(ans, now);
	}
	cout << ans << '\n';
	return 0;
}
// Nima

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:80:7: warning: unused variable 'w' [-Wunused-variable]
   80 |    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.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7392 KB Output is correct

Subtask #2
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7392 KB Output is correct
3 Incorrect 6 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #3
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7392 KB Output is correct
3 Incorrect 6 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7392 KB Output is correct
3 Incorrect 6 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7372 KB Output is correct
2 Correct 5 ms 7392 KB Output is correct
3 Incorrect 6 ms 7372 KB Output isn't correct
4 Halted 0 ms 0 KB -