oj.uz

Submission #5438

# Submission time Handle Problem Language Result Execution time Memory
5438 2014-05-02T09:45:07 Z gs12117 Toll (APIO13_toll) C++
56 / 100
 2500 ms 9692 KB 
#include<stdio.h>
#include<algorithm>
int n,p,m;
int etob[23][2];
long long int ans;
struct edge{
	int a,b,cost;
	bool operator<(const edge&r)const{
		return cost<r.cost;
	}
};
edge eip[300100];
int uft[100100];
long long int pn[100100];
long long int npn[100100];
int neb[23][2];
int nebn;
int chk[300100];
int ufs[100100];
int es[100100];
int elist[45][2];
int price[23];
int bchk[100100];
long long int snum[100100];
long long int nans;
int uftf(int x){
	if(x==uft[x])return x;
	return uft[x]=uftf(uft[x]);
}
void fillpath(int x,int y,int val){
	int i;
	bchk[x]=1;
	if(x==y)return;
	for(i=es[x];i<es[x+1];i++){
		if(bchk[elist[i][0]]==0){
			fillpath(elist[i][0],y,val);
			if(bchk[y]==1){
				if(price[elist[i][1]]>val)price[elist[i][1]]=val;
				return;
			}
		}
	}
}
void dfs(int x){
	int i;
	bchk[x]=1;
	snum[x]=npn[x];
	for(i=es[x];i<es[x+1];i++){
		if(bchk[elist[i][0]]==0){
			dfs(elist[i][0]);
			snum[x]+=snum[elist[i][0]];
			nans+=snum[elist[i][0]]*elist[i][1];
		}
	}
}
void calc(int x){
	int i,j;
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<p;i++){
		if((x>>i)%2==1){
			if(uftf(etob[i][0])==uftf(etob[i][1]))return;
			uft[uftf(etob[i][0])]=uftf(etob[i][1]);
		}
	}
	for(i=0;i<m;i++){
		chk[i]=0;
		if(uftf(eip[i].a)!=uftf(eip[i].b)){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
			chk[i]=1;
		}
	}
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(chk[i]==1){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=1;i<=n;i++){
		npn[i]=0;
	}
	for(i=1;i<=n;i++){
		npn[uftf(i)]+=pn[i];
		ufs[i]=uftf(i);
	}
	nebn=0;
	for(i=0;i<p;i++){
		if((x>>i)%2==1){
			neb[nebn][0]=uftf(etob[i][0]);
			neb[nebn][1]=uftf(etob[i][1]);
			price[nebn]=999999999;
			nebn++;
		}
	}
	for(i=0;i<n+3;i++){
		es[i]=0;
	}
	for(i=0;i<nebn;i++){
		es[neb[i][0]+2]++;
		es[neb[i][1]+2]++;
	}
	for(i=0;i<n+3;i++){
		es[i+1]+=es[i];
	}
	for(i=0;i<nebn;i++){
		elist[es[neb[i][0]+1]][0]=neb[i][1];
		elist[es[neb[i][0]+1]][1]=i;
		es[neb[i][0]+1]++;
		elist[es[neb[i][1]+1]][0]=neb[i][0];
		elist[es[neb[i][1]+1]][1]=i;
		es[neb[i][1]+1]++;
	}
	for(i=1;i<=n;i++){
		uft[i]=i;
	}
	for(i=0;i<m;i++){
		if(chk[i]==1){
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=0;i<m;i++){
		if(uftf(eip[i].a)!=uftf(eip[i].b)){
			for(j=1;j<=n;j++){
				bchk[j]=0;
			}
			fillpath(ufs[eip[i].a],ufs[eip[i].b],eip[i].cost);
			uft[uftf(eip[i].a)]=uftf(eip[i].b);
		}
	}
	for(i=0;i<2*nebn;i++){
		elist[i][1]=price[elist[i][1]];
	}
	for(j=1;j<=n;j++){
		bchk[j]=0;
		snum[j]=0;
	}
	nans=0;
	dfs(ufs[1]);
	if(ans<nans)ans=nans;
}
int main(){
	int i,j;
	scanf("%d%d%d",&n,&m,&p);
	for(i=0;i<m;i++){
		scanf("%d%d%d",&eip[i].a,&eip[i].b,&eip[i].cost);
	}
	for(i=0;i<p;i++){
		scanf("%d%d",&etob[i][0],&etob[i][1]);
	}
	for(i=1;i<=n;i++){
		scanf("%lld",&pn[i]);
	}
	std::sort(eip,eip+m);
	for(i=1;i<(1<<p);i++){
		calc(i);
	}
	printf("%lld",ans);
}

Subtask #1
16.0 / 16.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 9692 KB Output is correct
2 Correct 0 ms 9692 KB Output is correct

Subtask #2
18.0 / 18.0

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

Subtask #3
22.0 / 22.0

# Verdict Execution time Memory Grader output
1 Correct 352 ms 9692 KB Output is correct
2 Correct 168 ms 9692 KB Output is correct

Subtask #4
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Execution timed out 2500 ms 9688 KB Program timed out
2 Halted 0 ms 0 KB -

Subtask #5
0.0 / 22.0

# Verdict Execution time Memory Grader output
1 Halted 0 ms 0 KB -