Submission #438759

#	Time	Username	Problem	Language	Result	Execution time	Memory
438759		soroush	Toll (APIO13_toll)	C++17	0 / 100	5 ms	7628 KiB

toll

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<int , int> pii;

mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());

const int maxn = 1e5 + 10;
const ll mod = 1e9+7;

#define pb push_back
#define endl '\n'
#define dokme(x) cout << x , exit(0)
#define ms(x , y) memset(x , y , sizeof x)
ll pw(ll a, ll b, ll md = mod){ll res = 1;while(b){if(b&1){res=(a*res)%md;}a=(a*a)%md;b>>=1;}return(res);}

int n, m, k;
vector < int > adj[maxn] , mst;
vector < pii > e;
int a[maxn] , b[maxn] , c[maxn] , p[maxn] , srt[maxn] , par[maxn];

int getpar(int v){
	return ((par[v]) ? par[v] = getpar(par[v]) : v);
}

void merge(int x){
	int v = getpar(a[x]) , u = getpar(b[x]);
	if(u == v)return;
	par[v] = u;
	mst.pb(x);
}

const int lg = 20;

struct LCA{
	int n;
	int par[lg+3][maxn] , h[maxn];
	vector < pii > adj[maxn];
	ll H[maxn] , sum[maxn];
	void dfs(int v  , int pr){
		sum[v] += p[v];
		for(auto [u, w] : adj[v]) if(u ^ pr)
			H[u] = H[v] + w , h[u] = h[v] + 1 , par[0][u] = v , dfs(u , v) , sum[v] += sum[u];
	}
	void init(int N , int root = 1){
		n = N;
		dfs(root , 0);
		h[0] = -1;
		for(int j = 1 ; j <= lg ; j ++)
			for(int i = 1 ; i <= n ; i ++)
				par[j][i] = par[j - 1][par[j - 1][i]];
	}
	int lca(int u , int v){
		if(h[u] < h[v])
			swap(u , v);
		for(int i = lg ; i >= 0 ; i --)
			if(h[par[i][u]] >= h[v])
				u = par[i][u];
		if(u == v)
			return(u);
		for(int i = lg ; i >= 0 ; i --)
			if(par[i][u] ^ par[i][v])
				u = par[i][u] , v = par[i][v];
		return(par[0][v]);
	}
	int uwdist(int u , int v){
		return h[u] + h[v] - 2 * h[lca(u , v)];
	}
	int dist(int u , int v){
		return(H[u] + H[v] - 2*H[lca(u , v)]);
	}
}lc, cur;


int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	for(int i = 0 ; i < m ; i ++){
		cin >> a[i] >> b[i] >> c[i];
		adj[a[i]].pb(i), adj[b[i]].pb(i);
		srt[i] = i;
	}
	for(int i = 0 , u , v ; i < k ; i ++)
		cin >> u >> v, e.pb({u , v});
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i];
	sort(srt , srt + n , [](int i , int j){return c[i] < c[j];});
	for(int i = 1 ; i <= n ; i ++)
		sort(adj[i].begin(), adj[i].end() , [](int i, int j){return c[i] < c[j];});
	for(int i = 0 ; i < m ; i ++)
		merge(srt[i]);
	ll sum = 0;
	for(int x : mst){
		lc.adj[a[x]].pb({b[x] , c[x]});
		lc.adj[b[x]].pb({a[x] , c[x]});
		sum += c[x];
	}
	lc.init(n);
	ll ans = 0;
	for(int i = 0 ; i < (1 << k) ; i ++){
		bool ok = 1;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			if(getpar(u) == getpar(v)){
				ok = 0;
				for(auto [a, b] : e)par[a] = par[b] = 0;
				break;
			}
			par[getpar(v)] = getpar(u);
		}
		if(!ok)continue;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			cur.adj[u].pb({v, 0}) , cur.adj[v].pb({u , 0});
		}
		mst.clear();
		for(int i = 0 ; i < m ; i ++)
			merge(srt[i]);
		for(int x : mst){
			cur.adj[a[x]].pb({b[x] , c[x]});
			cur.adj[b[x]].pb({a[x] , c[x]});
			sum -= c[x];
		}
		cur.init(n);
		for(int i = 1 ; i <= n ; i ++)par[i] = 0;
		for(int j = 0 ; j < k ; j ++)if(i & (1 << j)){
			int u = e[j].first, v = e[j].second;
			int lca = cur.lca(u, v);
			ans += sum * (cur.sum[u ^ v ^ lca]);
		}
	}
	cout << ans;
	return(0);
}

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