#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.y < b.y || (a.y == b.y && a.x < b.x ) ; }
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) ) ;
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( calc(l.first,l.second) == calc(res.first, res.second) )
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: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 ) ;
~~~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
5 ms |
256 KB |
Output is correct |
| 2 |
Correct |
5 ms |
256 KB |
Output is correct |
| 3 |
Correct |
5 ms |
256 KB |
Output is correct |
| 4 |
Correct |
5 ms |
376 KB |
Output is correct |
| 5 |
Correct |
5 ms |
376 KB |
Output is correct |
| 6 |
Correct |
5 ms |
376 KB |
Output is correct |
| 7 |
Correct |
6 ms |
376 KB |
Output is correct |
| 8 |
Correct |
11 ms |
760 KB |
Output is correct |
| 9 |
Correct |
5 ms |
256 KB |
Output is correct |
| 10 |
Correct |
5 ms |
256 KB |
Output is correct |
| 11 |
Correct |
5 ms |
376 KB |
Output is correct |
| 12 |
Correct |
5 ms |
256 KB |
Output is correct |
| 13 |
Correct |
6 ms |
256 KB |
Output is correct |
| 14 |
Correct |
11 ms |
376 KB |
Output is correct |
| 15 |
Correct |
10 ms |
376 KB |
Output is correct |
| 16 |
Correct |
100 ms |
376 KB |
Output is correct |
| 17 |
Correct |
107 ms |
376 KB |
Output is correct |
| 18 |
Correct |
95 ms |
376 KB |
Output is correct |
| 19 |
Correct |
720 ms |
852 KB |
Output is correct |
| 20 |
Correct |
742 ms |
756 KB |
Output is correct |
