답안 #145870

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
145870 2019-08-21T08:45:40 Z TadijaSebez 시간이 돈 (balkan11_timeismoney) C++11
45 / 100
2000 ms 65536 KB
#include <bits/stdc++.h>
using namespace std;
#define ldb long double
#define ll long long
#define pb push_back
#define mp make_pair
struct Edge
{
	int u,v,a,b;
	Edge(){}
	Edge(int _u, int _v, int _a, int _b):u(_u),v(_v),a(_a),b(_b){}
	ll Get(ll ma, ll mb){ return ma*a+mb*b;}
};
vector<Edge> edges;
vector<pair<int,int>> tree;
ll ma,mb;
bool comp(Edge x, Edge y)
{
	return x.Get(ma,mb)<y.Get(ma,mb);
}
const int N=205;
struct DSU
{
	int p[N];
	void init(){ for(int i=0;i<N;i++) p[i]=i;}
	DSU(){ init();}
	int Find(int x){ return x==p[x]?x:p[x]=Find(p[x]);}
	void Union(int x, int y){ p[Find(x)]=Find(y);}
} DS;
ll ans=9e18;
ll ans_ma,ans_mb;
pair<int,int> MST(ll ma, ll mb)
{
	DS.init();
	tree.clear();
	::ma=ma;::mb=mb;
	sort(edges.begin(),edges.end(),comp);
	int A=0,B=0;
	for(Edge e:edges)
	{
		if(DS.Find(e.u)!=DS.Find(e.v))
		{
			DS.Union(e.u,e.v);
			A+=e.a;
			B+=e.b;
			tree.pb({e.u,e.v});
		}
	}
	ans=min(ans,(ll)A*B);
	if(ans==(ll)A*B) ans_ma=ma,ans_mb=mb;
	return {A,B};
}
ll cross(pair<int,int> x, pair<int,int> y){ return (ll)x.first*y.second-(ll)x.second*y.first;}
pair<int,int> operator - (pair<int,int> x, pair<int,int> y){ return mp(x.first-y.first,x.second-y.second);}
bool below(pair<int,int> z, pair<int,int> x, pair<int,int> y)
{
	return cross(z-x,y-x)!=0;
}
void Solve(pair<int,int> F, pair<int,int> S)
{
	pair<int,int> M=MST(S.first-F.first,F.second-S.second);
	if(below(M,F,S))
	{
		Solve(F,M);
		Solve(M,S);
	}
}
int main()
{
	int n,m,u,v,a,b;
	scanf("%i %i",&n,&m);
	for(int i=1;i<=m;i++) scanf("%i %i %i %i",&u,&v,&a,&b),u++,v++,edges.pb(Edge(u,v,a,b));
	pair<int,int> F=MST(1,0);
	pair<int,int> S=MST(0,1);
	Solve(F,S);
	pair<int,int> sol=MST(ans_ma,ans_mb);
	printf("%i %i\n",sol.first,sol.second);
	for(auto e:tree) printf("%i %i\n",e.first-1,e.second-1);
	return 0;
}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:71:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%i %i",&n,&m);
  ~~~~~^~~~~~~~~~~~~~~
timeismoney.cpp:72:64: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  for(int i=1;i<=m;i++) scanf("%i %i %i %i",&u,&v,&a,&b),u++,v++,edges.pb(Edge(u,v,a,b));
                        ~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~~~~~~~~
# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 256 KB Output is correct
3 Correct 2 ms 256 KB Output is correct
4 Correct 2 ms 256 KB Output is correct
5 Correct 2 ms 256 KB Output is correct
6 Correct 2 ms 376 KB Output is correct
7 Correct 4 ms 376 KB Output is correct
8 Correct 9 ms 808 KB Output is correct
9 Correct 2 ms 376 KB Output is correct
10 Runtime error 1523 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
11 Runtime error 1119 ms 65536 KB Execution killed with signal 9 (could be triggered by violating memory limits)
12 Execution timed out 2052 ms 40880 KB Time limit exceeded
13 Execution timed out 2060 ms 42216 KB Time limit exceeded
14 Execution timed out 2025 ms 6020 KB Time limit exceeded
15 Execution timed out 2055 ms 7336 KB Time limit exceeded
16 Execution timed out 2061 ms 1324 KB Time limit exceeded
17 Execution timed out 2061 ms 1420 KB Time limit exceeded
18 Execution timed out 2057 ms 1252 KB Time limit exceeded
19 Execution timed out 2062 ms 1012 KB Time limit exceeded
20 Execution timed out 2054 ms 1036 KB Time limit exceeded