oj.uz

답안 #83050

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
83050 2018-11-04T11:51:14 Z farukkastamonuda 시간이 돈 (balkan11_timeismoney) C++14
100 / 100
 623 ms 784 KB 
#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;
}

Compilation message

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

# 결과 실행 시간 메모리 Grader output
1 Correct 9 ms 376 KB Output is correct
2 Correct 3 ms 500 KB Output is correct
3 Correct 3 ms 500 KB Output is correct
4 Correct 5 ms 500 KB Output is correct
5 Correct 16 ms 504 KB Output is correct
6 Correct 13 ms 504 KB Output is correct
7 Correct 78 ms 520 KB Output is correct
8 Correct 376 ms 776 KB Output is correct
9 Correct 2 ms 776 KB Output is correct
10 Correct 3 ms 776 KB Output is correct
11 Correct 3 ms 776 KB Output is correct
12 Correct 5 ms 776 KB Output is correct
13 Correct 5 ms 776 KB Output is correct
14 Correct 26 ms 776 KB Output is correct
15 Correct 16 ms 776 KB Output is correct
16 Correct 104 ms 776 KB Output is correct
17 Correct 101 ms 776 KB Output is correct
18 Correct 122 ms 776 KB Output is correct
19 Correct 623 ms 784 KB Output is correct
20 Correct 611 ms 784 KB Output is correct