Submission #231806

#	Time	Username	Problem	Language	Result	Execution time	Memory
231806		alishahali1382	Toll (APIO13_toll)	C++14	100 / 100	1997 ms	23140 KiB

toll

#include <bits/stdc++.h>
#pragma GCC optimize ("O2")
#pragma GCC optimize ("unroll-loops")
//#pragma GCC optimize("no-stack-protector,fast-math")

using namespace std;
typedef long long ll;
typedef long double ld;
typedef pair<int, int> pii;
typedef pair<pii, int> piii;
typedef pair<ll, ll> pll;
#define debug(x) cerr<<#x<<'='<<(x)<<endl;
#define debugp(x) cerr<<#x<<"= {"<<(x.first)<<", "<<(x.second)<<"}"<<endl;
#define debug2(x, y) cerr<<"{"<<#x<<", "<<#y<<"} = {"<<(x)<<", "<<(y)<<"}"<<endl;
#define debugv(v) cerr<<#v<<" : ";for (auto x:v) cerr<<x<<' ';cerr<<endl;
#define all(x) x.begin(), x.end()
#define pb push_back
#define kill(x) return cout<<x<<'\n', 0;

const ld eps=1e-7;
const int inf=1000000010;
const ll INF=10000000000000010LL;
const int mod = 1000000007;
const int MAXN = 300030, K=20;

ll n, m, k, u, v, x, y, t, a, b, ans;
int par[MAXN];
int E[MAXN][3];
int ind[MAXN];
ll P[MAXN];
bool good1[MAXN], good2[MAXN];
int parent[MAXN], parid[MAXN], h[MAXN];
ll sz[MAXN];
vector<pii> G[MAXN];

int getpar(int x){
	if (par[x]==x) return x;
	return par[x]=getpar(par[x]);
}

int join(int x, int y){
	x=getpar(x);
	y=getpar(y);
	if (x==y) return 0;
	par[x]=y;
	return 1;
}

void dfs(int node){
	sz[node]=P[node];
	for (pii p:G[node]) if (p.first!=parent[node]){
		parent[p.first]=node;
		parid[p.first]=p.second;
		h[p.first]=h[node]+1;
		dfs(p.first);
		sz[node]+=sz[p.first];
	}
}

int main(){
	ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
	//freopen("input.txt", "r", stdin);
	//freopen("output.txt", "w", stdout);
	cin>>n>>m>>k;
	vector<pair<int, pii>> vec;
	while (m--){
		cin>>u>>v>>x;
		vec.pb({x, {u, v}});
	}
	sort(all(vec));
	m=0;
	for (auto p:vec){
		E[m][0]=p.second.first;
		E[m][1]=p.second.second;
		E[m++][2]=p.first;
	}
	
	for (int i=m; i<m+k; i++) cin>>E[i][0]>>E[i][1];
	for (int i=1; i<=n; i++) cin>>P[i];
	
	iota(par+1, par+n+1, 1);
	for (int i=0; i<m; i++) good1[i]=join(E[i][0], E[i][1]);
	
	iota(par+1, par+n+1, 1);
	for (int i=m; i<m+k; i++) join(E[i][0], E[i][1]);
	for (int i=0; i<m; i++) good2[i]=join(E[i][0], E[i][1]);
	
	
	vector<int> edge, V;
	iota(par+1, par+n+1, 1);
	for (int i=0; i<m; i++){
		if (good2[i]) join(E[i][0], E[i][1]);
		else if (good1[i]) edge.pb(i);
	}
	
	for (int i=0; i<m+k; i++) E[i][0]=getpar(E[i][0]), E[i][1]=getpar(E[i][1]);
	for (int i=1; i<=n; i++){
		if (par[i]!=i) P[getpar(i)]+=P[i], P[i]=0;
		else V.pb(i);
	}
	
	int root=getpar(1);
	
	for (int mask=0; mask<(1<<k); mask++){
		for (int v:V){
			par[v]=v;
			G[v].clear();
		}
		
		bool bad=0;
		for (int i=0; i<k && !bad; i++) if (mask&(1<<i)){
			int u=E[i+m][0], v=E[i+m][1];
			if (join(u, v)){
				G[u].pb({v, i+m});
				G[v].pb({u, i+m});
				E[i+m][2]=inf;
			}
			else bad=1;
		}
		if (bad) continue ;
		
		for (int e:edge){
			int u=E[e][0], v=E[e][1];
			if (join(u, v)){
				G[u].pb({v, e});
				G[v].pb({u, e});
			}
		}
		
		// should it be connected?!
		
		dfs(root);
		for (int e:edge){
			int u=E[e][0], v=E[e][1], w=E[e][2];
			while (u!=v){
				if (h[u]>h[v]) swap(u, v);
				if (parid[v]>=m) E[parid[v]][2]=min(E[parid[v]][2], w);
				v=parent[v];
			}
		}
		
		ll val=0;
		for (int v:V) if (parid[v]>=m) val+=sz[v]*E[parid[v]][2];
		
		ans=max(ans, val);
	}
	cout<<ans<<'\n';
	
	
	return 0;
}

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