Submission #439819

#	Time	Username	Problem	Language	Result	Execution time	Memory
439819		soroush	Toll (APIO13_toll)	C++17	100 / 100	1588 ms	18576 KiB

toll

#pragma GCC optimize("O2,unroll-loops")
#pragma GCC target("sse,sse2,avx,avx2,fma,popcnt")
#include <bits/stdc++.h>

using namespace std;

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

const int maxn = 1e5 + 10;

#define pb push_back
#define ms(x , y) memset(x , y , sizeof x)

int n, m , k;
int a[maxn*3], b[maxn*3], c[maxn*3] , srt[maxn*3] , p[maxn];
int L[maxn], R[maxn], num[maxn] , cnt;
ll sum[maxn], sub[22];
int par[maxn];
vector < int > adj[maxn], mst , e;
int E[22], Eptr = 0;
int ad[22][22][2], adptr[22];
int per[22];

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

bool merge (int u , int v){
	if((u = getpar(u)) == (v = getpar(v)))return 0;
	par[u] = v;return 1;
}

int gatpar(int v){
	return ((per[v]) ? per[v] = gatpar(per[v]) : v);
}

bool marge (int u , int v){
	if((u = gatpar(u)) == (v = gatpar(v)))return 0;
	per[u] = v;return 1;
}

void col(int v){
	num[v] = cnt; sum[cnt] += p[v];
	for(auto u : adj[v])if(!num[u]) col(u);
}

int Par[40] , counts[40] , h[40] , mn[40];

void dfs(int v){
	sub[v] = sum[v];
	for(int i = 0 ; i < adptr[v] ; i ++){
		int u = ad[v][i][0] , x = ad[v][i][1];
		if(u ^ Par[v]){
		Par[u] = v , counts[u] = x , h[u] = h[v] + 1;
		dfs(u);
		sub[v] += sub[u];
	}}
}

ll solve(int msk){
	ll ans = 0;
	ms(per , 0);
	for(int i = 0 ; i < k ; i ++)if(msk & (1 << i)){
		if(!marge(L[i] , R[i]))return 0;
	}
	ms(adptr , 0);
	for(int i = 0 ; i < k ; i ++)if(msk & (1 << i)){
		ad[L[i]][adptr[L[i]]][0] = R[i];
		ad[L[i]][adptr[L[i]] ++ ][1] = 1;
		ad[R[i]][adptr[R[i]]][0] = L[i] ,
		ad[R[i]][adptr[R[i]] ++ ][1] = 1;
	}
	Eptr = 0;
	for(int i : e)
		if(marge(a[i] , b[i])){
			ad[a[i]][adptr[a[i]]][0] = b[i];
			ad[a[i]][adptr[a[i]] ++ ][1] = 0;
			ad[b[i]][adptr[b[i]]][0] = a[i] ,
			ad[b[i]][adptr[b[i]] ++ ][1] = 0;
		}
		else 
			E[Eptr++] = i;
	dfs(1);
	ms(mn , 63);
	for(int i = 0 ; i < Eptr ; i ++){
		int e = E[i];
		int u = a[e] , v = b[e] , w = c[e];
		if(h[u] < h[v])swap(u , v);
		while(h[u] ^ h[v]){
			mn[u] = min(mn[u] , w) ,  u = Par[u];
		}
		while(u ^ v)
			mn[u] = min(mn[u] , w) , u = Par[u],
			mn[v] = min(mn[v] , w) , v = Par[v];
	}
	for(int i = 1 ; i <= cnt ; i ++)
		ans += counts[i] * sub[i] * mn[i];
	return ans;
}

int32_t main(){
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin >> n >> m >> k;
	mst.reserve(32);
	e.reserve(32);
	for(int i = 1 ; i <= m ; i ++)
		cin >> a[i] >> b[i] >> c[i] , srt[i] = i;
	sort(srt + 1 , srt + m + 1 , [](int i , int j){return c[i] < c[j];});
	for(int i = 0 ; i < k ; i ++)	
		cin >> L[i] >> R[i];
	for(int i = 1 ; i <= n ; i ++)
		cin >> p[i];
	for(int i = 1 ; i <= m ; i ++)
		if(merge(a[srt[i]] , b[srt[i]]))mst.pb(srt[i]);
	fill(par + 1, par + n + 1, 0);
	for(int i = 0 ; i < k ; i ++)
		merge(L[i] , R[i]);
	for(int i : mst)
		if(merge(a[i] , b[i]))
			adj[a[i]].pb(b[i]), adj[b[i]].pb(a[i]);
		else
			e.pb(i);
	for(int i = 1 ; i <= n ; i ++)if(!num[i])
		++cnt , col(i);
	for(int i = 0 ; i < k ; i++)
		L[i] = num[L[i]], R[i] = num[R[i]];
	for(auto x : e)
		a[x] = num[a[x]] , b[x] = num[b[x]];
	ll ans = 0;
	for(int i = 0 ; i < (1 << k) ; i ++)
		ans= max(ans , solve(i));
	cout << ans;
	return(0);
}

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