제출 #201016

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
201016		Lawliet	시간이 돈 (balkan11_timeismoney)	C++17	100 / 100	405 ms	1144 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;
typedef long long int lli;

const int MAXN = 210;
const int INF = 1000;

struct edge
{
	int U, V;
	lli t, c;
	lli val;

	edge(int U, int V, lli t, lli c) : U(U), V(V), t(t), c(c) {}

	bool operator < (edge a) { return val < a.val; }
};

class UnionFind
{
	public:

		int find(int cur)
		{
			if( pai[cur] == cur ) return cur;
			return pai[cur] = find( pai[cur] );
		}

		bool same(int U, int V) { return find( U ) == find( V ); }

		void join(int i, int j)
		{
			i = find( i ); j = find( j );

			if( i == j ) return;

			if( peso[i] < peso[j] ) swap( i , j );

			pai[j] = i;
			if( peso[i] == peso[j] ) peso[i]++; 
		}

		void init(int n)
		{
			for(int i = 1 ; i <= n ; i++)
			{
				pai[i] = i;
				peso[i] = 0;
			}
		}

	private:

		int pai[MAXN];
		int peso[MAXN];
};

int n, m;

lli optX;
lli optY;
lli optVal;

vector< edge > ans;
vector< edge > sweep;

UnionFind DSU;

void updateAnswer(lli val, lli X, lli Y)
{
	if( val >= optVal ) return;

	optX = X;
	optY = Y;
	optVal = val;
}

void buildMST(lli X, lli Y, lli& sT, lli& sC, bool answer = false)
{
	sT = sC = 0;
	DSU.init( n );

	for(int i = 0 ; i < m ; i++)
	{
		lli T = sweep[i].t;
		lli C = sweep[i].c;

		sweep[i].val = X*T + Y*C;
	}

	sort( sweep.begin() , sweep.end() );

	for(int i = 0 ; i < m ; i++)
	{
		int U = sweep[i].U;
		int V = sweep[i].V;

		if( !DSU.same( U , V ) )
		{
			DSU.join( U , V );

			sT += sweep[i].t;
			sC += sweep[i].c;

			if( answer ) ans.push_back( sweep[i] );
		}
	}
}

void lowerHull(lli x1, lli y1, lli x2, lli y2)
{
	lli dX = abs( x1 - x2 );
	lli dY = abs( y1 - y2 );

	lli newX, newY;

	buildMST( dY , dX , newX , newY );

	if( (y2 - y1)*(newX - x1) == (newY - y1)*(x2 - x1) ) return;

	updateAnswer( newX*newY , dY , dX );

	lowerHull( x1 , y1 , newX , newY );
	lowerHull( newX , newY , x2 , y2 );
}

int main()
{
	scanf("%d %d",&n,&m);

	optVal = 1000000000000000000LL;

	for(int i = 1 ; i <= m ; i++)
	{
		int U, V;
		lli t, c;
		scanf("%d %d %lld %lld",&U,&V,&t,&c);

		U++; V++;

		sweep.push_back( edge( U , V , t , c ) );
	}

	lli x1, y1;
	buildMST( INF , 1 , x1 , y1 );

	lli x2, y2;
	buildMST( 1 , INF , x2 , y2 );

	updateAnswer( x1*y1 , INF , 1 );
	updateAnswer( x2*y2 , 1 , INF );

	lowerHull( x1 , y1 , x2 , y2 );

	lli sT, sC;
	buildMST( optX , optY , sT , sC , true );

	printf("%lld %lld\n",sT,sC);

	for(int i = 0 ; i < n - 1 ; i++)
		printf("%d %d\n",ans[i].U - 1,ans[i].V - 1);
}

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

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:130: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:138:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d %lld %lld",&U,&V,&t,&c);
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~

• Subtask 1: 100 / 100