제출 #83050

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
83050		farukkastamonuda	시간이 돈 (balkan11_timeismoney)	C++14	100 / 100	623 ms	784 KiB

timeismoney

#include <bits/stdc++.h>
#define fi first
#define se second
#define lo long long 
#define inf 1000000009
#define md 1000000007
#define li 10005
#define mp make_pair
#define pb push_back
#define mid (l+r)/2
#define pi pair<int, pair<int, pair<int,int> > >
using namespace std;
int n,m,x,y,t,r1=256,r2,fa[205],mn=inf,tutty,mm,tutty2;
int sz[205];
pair<int, pair<int, pair<int,int> > > p[li];
vector< pair<int,int> > ans,ans2;
pair<int,int> son;
bool cmp(pi a,pi b){
	return r1*a.se.se.fi+r2*a.se.se.se<r1*b.se.se.fi+r2*b.se.se.se;
}
int dsu(int x){
	if(fa[x]==x) return x;
	return fa[x]=dsu(fa[x]);
}
pair<int,int> solve(){
	//printf("(");
	ans.clear();
	for(int i=0;i<n;i++) {fa[i]=i;sz[i]=1;}
	sort(p+1,p+m+1,cmp);
	int totalt=0,totalp=0;
	for(int i=1;i<=m;i++){
		int seh1=p[i].fi;
		int seh2=p[i].se.fi;
		int tm=p[i].se.se.fi;
		int pr=p[i].se.se.se;
		if(dsu(seh1)!=dsu(seh2)){
			ans.pb(mp(seh1,seh2));
			seh1=dsu(seh1);
			seh2=dsu(seh2);
			if(sz[seh1]<sz[seh2]) swap(seh1,seh2);
			totalt+=tm;
			totalp+=pr;
			sz[seh1]+=sz[seh2];
			fa[seh2]=seh1;
			//ans.pb(mp(seh1,seh2));
		}
	}
	return mp(totalt,totalp);
}
int main(){
	scanf("%d %d",&n,&m);
	for(int i=1;i<=m;i++){
		scanf("%d %d %d %d",&x,&y,&t,&mm);
		//printf("?");
		p[i]=mp(x,mp(y,mp(t,mm)));
	}
	//printf("?");
	for(int i=1;i<=256;i++){
		r2=i;
		pair<int,int> tmp=solve();
		if(tmp.fi*tmp.se<mn){
			mn=tmp.fi*tmp.se;
			son=tmp;
			ans2=ans;
		}
	}
	r2=256;
	for(int i=1;i<=256;i++){
		r1=i;
		pair<int,int> tmp=solve();
		if(tmp.fi*tmp.se<mn){
			mn=tmp.fi*tmp.se;
			son=tmp;
			ans2=ans;
		}
	}
	printf("%d %d\n",son.fi,son.se);
	for(int i=0;i<(int)ans2.size();i++){
		printf("%d %d\n",ans2[i].fi,ans2[i].se);
	}
	return 0;
}

컴파일 시 표준 에러 (stderr) 메시지

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:51:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d %d",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
timeismoney.cpp:53:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %d %d",&x,&y,&t,&mm);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100