oj.uz

답안 #200486

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
200486 2020-02-07T00:09:41 Z CaroLinda 시간이 돈 (balkan11_timeismoney) C++14
50 / 100
 2000 ms 8372 KB 
#include <bits/stdc++.h>

#define all(x) x.begin(),x.end()

const int INF = 1e9+10 ;
const int MAXN = 210 ;
const int MAXM = 1e4 + 10 ;

using namespace std ;

struct Edge
{

	int u , v , x , y ;

	Edge(int u=0, int v=0, int x=0, int y=0) : u(u) , v(v) , x(x) , y(y) {}

} ;

int N , M , U , V , X , Y , A , B ;
int ans = INF ,ansx , ansy , ansa , ansb ;
vector< pair<int,int > > resp ;
vector<Edge> edge ;

int calc(int x , int y) { return x * A + y * B ; }

bool cmp1(Edge a , Edge b) { return a.x < b.x || (a.x == b.x && a.y < b.y) ; }
bool cmp2( Edge a , Edge b ) { return a.x > b.x || (a.x == b.x && a.y < b.y  ) ; }
bool cmp3( Edge a , Edge b ) { return calc(a.x, a.y)  < calc(b.x, b.y) ; }

// -------------------------------
//Kruskal's algorithm
int pai[MAXN] ;
int find(int x) { return ( pai[x] == x ) ? x : (pai[x] = find(pai[x]) ) ; }
bool join(int a, int b)
{
	a = find(a) ; 
	b = find(b) ;

	if( a == b ) return false ;

	if( rand() % 2 == 1 ) pai[a] = b ;
	else pai[b] = a ;

	return true ;

}

pair<int,int> MST( vector<Edge> edg, int save = 0 )
{

	iota(pai, pai+N , 0) ;

	X = 0 , Y = 0 ;

	for(Edge e : edg ) 
		if( join( e.u , e.v ) )
		{
			X += e.x , Y += e.y ;
			if( save ) resp.push_back( make_pair(e.u,e.v) ) ;
		}

	return make_pair( X , Y ) ;

}
inline void remake( pair<int,int> p1 )
{
	if( ans <= p1.first * p1.second ) return ;
	ans = p1.first * p1.second ;
	ansx = p1.first ;
	ansy = p1.second ;
	ansa = A ;
	ansb = B ;
}
// -------------------------------

int main()
{
	scanf("%d%d", &N , &M ) ;
	for(int i = 1 ; i <= M ; i++ )
	{
		scanf("%d%d%d%d", &U, &V, &X, &Y ) ;
		edge.push_back( Edge(U,V,X,Y) ) ;
	}

	sort( all(edge) , cmp1 ) ;
	pair<int,int> p1 = MST( edge ) ;
	remake(p1) ;
	sort( all(edge) , cmp2 ) ;
	pair<int,int> p2 = MST(edge) ;
	remake(p2) ;

	queue< pair< pair<int,int> ,pair<int,int> > > fila ;

	fila.push( make_pair(p1,p2) ) ;

	int cnt = 1400 ;

	while( !fila.empty()  ) 
	{

		pair<int,int> l = fila.front().first ;
		pair<int,int> r = fila.front().second ;

		fila.pop() ;

		A = l.second - r.second ;
		B = -l.first + r.first ;

		sort(all(edge) , cmp3 ) ;

		pair<int,int> res = MST(edge) ;

		remake(res) ;

		if( res == l || res == r )
			continue ;

		fila.push( make_pair(l,res) ) ;
		fila.push( make_pair(res, r) ) ;

	}

	printf("%d %d\n" , ansx, ansy ) ;
	
	if( ansx == p1.first && ansy == p1.second )
	{
		sort(all(edge),cmp1) ;
		MST(edge, 1) ;
	}
	else if( ansx == p2.first && ansy == p2.second )
	{
		sort(all(edge), cmp2) ;
		MST(edge, 1) ;
	}
	else{
	A = ansa , B = ansb ;
	sort(all(edge),cmp3) ;
	MST(edge, 1) ;
	}
	for(auto p : resp ) printf("%d %d\n", p.first, p.second ) ;
	

}

Compilation message

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:97:6: warning: unused variable 'cnt' [-Wunused-variable]
  int cnt = 1400 ;
      ^~~
timeismoney.cpp:79: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:82:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d%d%d%d", &U, &V, &X, &Y ) ;
   ~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~

Subtask #1
50.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 5 ms 376 KB Output is correct
2 Correct 5 ms 256 KB Output is correct
3 Correct 5 ms 256 KB Output is correct
4 Execution timed out 2083 ms 8372 KB Time limit exceeded
5 Execution timed out 2089 ms 1812 KB Time limit exceeded
6 Execution timed out 2086 ms 2540 KB Time limit exceeded
7 Execution timed out 2092 ms 888 KB Time limit exceeded
8 Execution timed out 2089 ms 980 KB Time limit exceeded
9 Correct 5 ms 256 KB Output is correct
10 Correct 5 ms 256 KB Output is correct
11 Correct 5 ms 256 KB Output is correct
12 Correct 5 ms 256 KB Output is correct
13 Correct 5 ms 256 KB Output is correct
14 Correct 66 ms 376 KB Output is correct
15 Correct 13 ms 376 KB Output is correct
16 Execution timed out 2076 ms 772 KB Time limit exceeded
17 Execution timed out 2085 ms 760 KB Time limit exceeded
18 Execution timed out 2085 ms 600 KB Time limit exceeded
19 Execution timed out 2081 ms 760 KB Time limit exceeded
20 Execution timed out 2078 ms 760 KB Time limit exceeded