제출 #847380

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
847380		I_FloPPed21	시간이 돈 (balkan11_timeismoney)	C++14	40 / 100	8 ms	2628 KiB

timeismoney

#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;

}

• Subtask 1: 40 / 100