Submission #159534

#	Time	Username	Problem	Language	Result	Execution time	Memory
159534		HungAnhGoldIBO2020	Toll (APIO13_toll)	C++14	100 / 100	2455 ms	26056 KiB

toll

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int M=3e5+2;
const int N=1e5+2;
const int K=41;
const int inf=1e9+7;
vector<pair<int,pair<int,int> > > edge,tree,res,lis;
vector<pair<int,int> > damn,adj[N];
int head[N],grp[N],sum[K],a[N],max1[K],hihixd[K],level[K];
pair<int,int> par[K];
int findd(int x){
	if(head[x]<0){
		return x;
	}
	int y=findd(head[x]);
	head[x]=y;
	return y;
}
void unionn(int x,int y){
	x=findd(x),y=findd(y);
	head[x]+=head[y];
	head[y]=x;
}
bool samee(int x,int y){
	return findd(x)==findd(y);
}
void dfs(int x,int p){
	//cout<<x<<endl;
	grp[x]=grp[p];
	sum[grp[x]]+=a[x];
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i].first!=p){
			dfs(adj[x][i].first,x);
		}
	}
}
void dfs1(int x,int p){
	hihixd[x]=sum[x];
	for(int i=0;i<adj[x].size();i++){
		if(adj[x][i].first!=p){
			level[adj[x][i].first]=level[x]+1;
			dfs1(adj[x][i].first,x);
			hihixd[x]+=hihixd[adj[x][i].first];
			par[adj[x][i].first]={x,adj[x][i].second};
		}
	}
}
signed main(){
	ios::sync_with_stdio(0);
	cin.tie(0);
	int n,i,j,k,l,m,num,com=0,z;
	long long ans=0,hihi;
	cin>>n>>m>>num;
	for(i=1;i<=m;i++){
		cin>>j>>k>>l;
		edge.push_back({l,{j,k}});
	}
	for(i=1;i<=num;i++){
		cin>>j>>k;
		damn.push_back({j,k});
	}
	for(i=1;i<=n;i++){
		head[i]=-1;
	}
	sort(edge.begin(),edge.end());
	for(i=0;i<m;i++){
		j=edge[i].second.first;
		k=edge[i].second.second;
		//cout<<i<<' '<<edge[i].first<<' '<<j<<' '<<k<<endl;
		if(!samee(j,k)){
//			cout<<j<<' '<<k<<endl;
			unionn(j,k);
			tree.push_back(edge[i]);
		}
	}
//	cout<<"cac"<<endl;
	for(i=1;i<=n;i++){
		head[i]=-1;
	}
	for(i=1;i<=num;i++){
		j=damn[i-1].first;
		k=damn[i-1].second;
		if(!samee(j,k)){
//			cout<<j<<' '<<k<<endl;
			unionn(j,k);
		}
	}
	for(i=1;i<=n;i++){
		cin>>a[i];
	}
//	com=0;
	for(i=0;i<tree.size();i++){
		j=tree[i].second.first;
		k=tree[i].second.second;
		if(!samee(j,k)){
//			cout<<j<<' '<<k<<" cac"<<endl;
//			com++;
			unionn(j,k);
			adj[j].push_back({k,tree[i].first});
			adj[k].push_back({j,tree[i].first});
		}
		else{
			lis.push_back(tree[i]);
		}
	}
//	assert(com<=n-1-num);
	for(i=1;i<=n;i++){
		if(!grp[i]){
			com++;
			grp[i]=com;
			dfs(i,i);
		//	cout<<com<<' '<<i<<endl;
		}
	}
	//pre-computed is ok
//	cout<<(1<<num)<<endl;
	for(i=0;i<(1<<num);i++){
//		cout<<i<<endl;
		for(j=1;j<=com;j++){
			head[j]=-1;
			adj[j].clear();
			max1[j]=inf;
		}
		res.clear();
		bool cac=false;
		for(j=0;j<num;j++){
			k=grp[damn[j].first];
			l=grp[damn[j].second];
			if(((1<<j)&i)){
				if(samee(k,l)){
					cac=true;
					break;
				}
				unionn(k,l);
				adj[k].push_back({l,j+1});
				adj[l].push_back({k,j+1});
				//cout<<k<<' '<<l<<' '<<j+1<<endl;
			}
		}
		if(cac){
//			cout<<j<<' '<<k<<' '<<l<<endl;
			continue;
		}
	//	cout<<"lon"<<endl;
		for(j=0;j<lis.size();j++){
			k=grp[lis[j].second.first];
			l=grp[lis[j].second.second];
			if(!samee(k,l)){
				unionn(k,l);
				adj[k].push_back({l,0});
				adj[l].push_back({k,0});
			}
			else{
				res.push_back(lis[j]);
			}
		}
		dfs1(grp[1],grp[1]);
	//	cout<<"lon?"<<endl;	
		for(j=1;j<=com;j++){
			head[j]=-1;
		}
		for(j=0;j<res.size();j++){
			z=res[j].first;
			k=grp[res[j].second.first];
			l=grp[res[j].second.second];
			k=findd(k);
			l=findd(l);
//			cout<<k<<' '<<l<<' '<<res[j].second.first<<' '<<res[j].second.second<<endl;
			while(k!=l){
				if(level[k]<level[l]){
					swap(k,l);
				}
				max1[par[k].second]=min(max1[par[k].second],z);
			//	cout<<par[k].second<<endl;
				unionn(par[k].first,k);
				k=findd(k);
			}
		}
		//cout<<"concactrecon"<<endl;
		hihi=0;
		for(j=0;j<num;j++){
			if(((1<<j)&i)){
				k=grp[damn[j].first];
				l=grp[damn[j].second];
				if(level[k]<level[l]){
					swap(k,l);
				}
				hihi+=hihixd[k]*max1[j+1];
//				cout<<hihi
			}
		}
		ans=max(ans,hihi);
//		cout<<hihi<<' '<<i<<endl;
	}
	cout<<ans;
}
/*
5 5 1 
3 5 2 
1 2 3
2 3 5 
2 4 4 
4 3 6 
1 3 
10 20 30 40 50 
*/ 

Compilation message (stderr)

toll.cpp: In function 'void dfs(long long int, long long int)':
toll.cpp:32:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
toll.cpp: In function 'void dfs1(long long int, long long int)':
toll.cpp:40:15: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(int i=0;i<adj[x].size();i++){
              ~^~~~~~~~~~~~~~
toll.cpp: In function 'int main()':
toll.cpp:93:11: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
  for(i=0;i<tree.size();i++){
          ~^~~~~~~~~~~~
toll.cpp:146:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<lis.size();j++){
           ~^~~~~~~~~~~
toll.cpp:163:12: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
   for(j=0;j<res.size();j++){
           ~^~~~~~~~~~~

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