# | Time | Username | Problem | Language | Result | Execution time | Memory |
---|---|---|---|---|---|---|---|
847380 | I_FloPPed21 | timeismoney (balkan11_timeismoney) | C++14 | 8 ms | 2628 KiB |
This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
long long n, m ;
struct timp
{
long long a, b, c,d ;
} v [ 100005 ];
bool compare( timp x, timp y )
{
return ( x .c * x .d < y .c * y .d );
}
long long rad[ 200005 ];
long long get ( long long x )
{
long long baux = x ;
while ( rad [ baux ] > 0 )
{
baux = rad [ baux ] ;
}
while ( rad [ x ] > 0 )
{
long long txt = rad [x ];
rad [x ] = baux ;
x = txt ;
}
return baux ;
}
bool find (int x , int y )
{
return ( get(x) == get(y));
}
void unite ( int x, int y )
{
int a = get ( x ) ;
int b = get ( y ) ;
if ( a == b )
return ;
if ( rad[ a ] < rad [ b ])
{
rad [ a ] += rad[ b ] ;
rad [b ] = a;
}
else
{
rad [ b ] += rad[ a ];
rad [ a] = b;
}
}
int main()
{
//ios_base::sync_with_stdio(false);
//cin.tie(0);
//cout.tie(0);
cin >> n >> m ;
for ( int i = 1; i <= m ; i ++ )
{
cin >> v[ i ] . a>> v[ i ] . b >> v [ i ] . c>> v[ i ] . d;
}
sort ( v+ 1, v + m + 1,compare );
for (int i = 0; i <= n ; i ++ )
rad [ i] = -1 ;
long long val1 = 0, val2 = 0;
queue<pair<int,int>> q;
for( int i = 1; i <= m ; i ++ )
{
if ( find ( v [ i ] . a, v[ i ] . b ) == false )
{
unite ( v [i ] . a, v[ i ] . b ) ;
q.push({v[i].a,v[i].b});
val1 += v [i ].c ;
val2 += v[ i ] . d;
}
}
cout << val1 << " " << val2 << '\n';
while ( !q.empty())
{
cout << q.front().first << " " << q.front() .second << '\n';
q.pop();
}
return 0;
}
# | Verdict | Execution time | Memory | Grader output |
---|---|---|---|---|
Fetching results... |