oj.uz

Submission #417390

# Submission time Handle Problem Language Result Execution time Memory
417390 2021-06-03T16:09:44 Z kshitij_sodani Toll (APIO13_toll) C++14
56 / 100
 2500 ms 69396 KB 
//#pragma GCC optimize("Ofast,unroll-loops")
#include <bits/stdc++.h>
using namespace std;
typedef long long llo;
#define mp make_pair
#define pb push_back
#define a first 
#define b second
#define endl '\n'


llo t;
llo par[1000001];
llo par2[1000001];
vector<pair<llo,llo>> adj[1000001];
llo it[1000001];

llo find(llo no){
	if(par[no]==no){
		return par[no];
	}
	par[no]=find(par[no]);
	return par[no];
}
llo co=0;
llo st[1000001];
llo endd[1000001];
bool vis[600001];
llo ss[100001];
llo val[100001];
//llo par2[100001];
void dfs(llo no,llo par=-1){
	st[no]=co;
	co++;
	par2[no]=par;
	ss[no]=it[no];
	//cout<<no<<"<"<<endl;
	for(auto j:adj[no]){
		//cout<<no<<":"<<j.a<<":"<<j.b<<endl;
		if(vis[j.b]==0){
			continue;
		}
		if(j.a!=par){
			dfs(j.a,no);
			ss[no]+=ss[j.a];
		}
	}
	endd[no]=co-1;
}
bool ispar(llo x,llo y){
	return st[x]<=st[y] and endd[x]>=endd[y];
}
int main(){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	llo n,m,k;
	cin>>n>>m>>k;
	vector<pair<llo,pair<llo,llo>>> ed;
	for(llo i=0;i<m;i++){
		llo aa,bb,cc;
		cin>>aa>>bb>>cc;
		aa--;
		bb--;
		ed.pb({cc,{aa,bb}});
		
	}
	sort(ed.begin(),ed.end());
	for(llo i=0;i<ed.size();i++){
		llo aa=ed[i].b.a;
		llo bb=ed[i].b.b;
		//cout<<aa<<"."<<bb<<"."<<i<<endl;
		adj[aa].pb({bb,i});
		adj[bb].pb({aa,i});
	}
	vector<pair<llo,llo>> zz;
	for(llo i=0;i<k;i++){
		llo aa,bb;
		cin>>aa>>bb;
		aa--;
		bb--;
		zz.pb({aa,bb});
		adj[aa].pb({bb,m+i});
		adj[bb].pb({aa,m+i});
	}
	for(llo i=0;i<n;i++){
		cin>>it[i];
	}
	llo ans=0;
	vector<pair<llo,pair<llo,llo>>> dd;

	for(llo i=1;i<(1<<k);i++){
		for(llo j=0;j<n;j++){
			par[j]=j;
			//adj[i].clear();
		}
		for(llo j=0;j<m+k;j++){
			vis[j]=0;
		}
		llo st=1;
		for(llo j=0;j<k;j++){
			if((1<<j)&i){
				
				llo x=find(zz[j].a);
				llo y=find(zz[j].b);
				if(x==y){
					st=0;
					break;
				}
				vis[j+m]=1;
				par[x]=y;
				//cout<<j+m<<":"<<endl;
			//	adj[zz[j].a].pb(zz[j].b);
			//	adj[zz[j].b].pb(zz[j].a);

			}
		}
		if(st==0){
			continue;
		}
		dd.clear();
		llo ind2=-1;
		for(auto j:ed){
			ind2++;
			llo x=find(j.b.a);
			llo y=find(j.b.b);
			if(x!=y){
				vis[ind2]=1;
			//	cout<<ind2<<","<<endl;
				par[x]=y;
				continue;
				//adj[j.b.a].pb(j.b.b);
				//adj[j.b.b].pb(j.b.a);
			}
			else{
				dd.pb(j);
			}
		}
		//continue;
		co=0;
		dfs(0);
		//cout<<endl;
		for(llo j=0;j<n;j++){
			par[j]=par2[j];
			val[j]=1e9;
		}
		//continue;
		for(auto j:dd){
			llo x=j.b.a;//find(j.b.a);
			llo y=j.b.b;//find(j.b.b);
			llo cur=x;
			vector<llo> xx;
			//continue;
			if(!ispar(x,y)){
				while(!ispar(cur,y)){
					xx.pb(cur);

					//cout<<cur<<",";
					cur=par[cur];	
				}
				//cout<<endl;
			}
			for(llo ii=0;ii<xx.size();ii++){
				val[xx[ii]]=min(val[xx[ii]],(llo)j.a);
				par[xx[ii]]=cur;
			}
			cur=y;
			xx.clear();
			if(!ispar(y,x)){
				while(!ispar(cur,x)){
					xx.pb(cur);
					cur=par[cur];	
				}
			}
			for(llo ii=0;ii<xx.size();ii++){
				val[xx[ii]]=min(val[xx[ii]],(llo)j.a);
				par[xx[ii]]=cur;
			}
		}
		llo su=0;
		for(llo j=0;j<k;j++){
			if((1<<j)&i){
				if(ispar(zz[j].a,zz[j].b)){
					su+=ss[zz[j].b]*val[zz[j].b];
				}
				else{
					su+=ss[zz[j].a]*val[zz[j].a];
				}
			}
		}
		ans=max(ans,su);
	}
	cout<<ans<<endl;











	return 0;
}

Compilation message

toll.cpp: In function 'int main()':
toll.cpp:68:15: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<std::pair<long long int, std::pair<long long int, long long int> > >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   68 |  for(llo i=0;i<ed.size();i++){
      |              ~^~~~~~~~~~
toll.cpp:162:19: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  162 |    for(llo ii=0;ii<xx.size();ii++){
      |                 ~~^~~~~~~~~~
toll.cpp:174:19: warning: comparison of integer expressions of different signedness: 'llo' {aka 'long long int'} and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  174 |    for(llo ii=0;ii<xx.size();ii++){
      |                 ~~^~~~~~~~~~

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct

Subtask #2
18.0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 17 ms 23812 KB Output is correct
4 Correct 17 ms 23844 KB Output is correct

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 17 ms 23812 KB Output is correct
4 Correct 17 ms 23844 KB Output is correct
5 Correct 486 ms 24560 KB Output is correct
6 Correct 256 ms 24452 KB Output is correct

Subtask #4
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 17 ms 23812 KB Output is correct
4 Correct 17 ms 23844 KB Output is correct
5 Correct 486 ms 24560 KB Output is correct
6 Correct 256 ms 24452 KB Output is correct
7 Execution timed out 2574 ms 69396 KB Time limit exceeded
8 Halted 0 ms 0 KB -

Subtask #5
0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 23756 KB Output is correct
2 Correct 13 ms 23756 KB Output is correct
3 Correct 17 ms 23812 KB Output is correct
4 Correct 17 ms 23844 KB Output is correct
5 Correct 486 ms 24560 KB Output is correct
6 Correct 256 ms 24452 KB Output is correct
7 Execution timed out 2574 ms 69396 KB Time limit exceeded
8 Halted 0 ms 0 KB -