oj.uz

Submission #159534

# Submission time Handle Problem Language Result Execution time Memory
159534 2019-10-23T04:02:13 Z HungAnhGoldIBO2020 Toll (APIO13_toll) C++14
100 / 100
 2455 ms 26056 KB 
#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

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.0 / 16.0

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

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3128 KB Output is correct
6 Correct 7 ms 3128 KB Output is correct

Subtask #4
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3128 KB Output is correct
6 Correct 7 ms 3128 KB Output is correct
7 Correct 289 ms 25960 KB Output is correct
8 Correct 302 ms 25872 KB Output is correct
9 Correct 293 ms 25880 KB Output is correct

Subtask #5
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 2680 KB Output is correct
2 Correct 4 ms 2680 KB Output is correct
3 Correct 5 ms 2680 KB Output is correct
4 Correct 5 ms 2680 KB Output is correct
5 Correct 7 ms 3128 KB Output is correct
6 Correct 7 ms 3128 KB Output is correct
7 Correct 289 ms 25960 KB Output is correct
8 Correct 302 ms 25872 KB Output is correct
9 Correct 293 ms 25880 KB Output is correct
10 Correct 2058 ms 25800 KB Output is correct
11 Correct 2445 ms 26056 KB Output is correct
12 Correct 2455 ms 23824 KB Output is correct