oj.uz

Submission #847380

# Submission time Handle Problem Language Result Execution time Memory
847380 2023-09-09T14:48:34 Z I_FloPPed21 timeismoney (balkan11_timeismoney) C++14
40 / 100
 8 ms 2628 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2392 KB Output is correct
2 Correct 1 ms 2392 KB Output is correct
3 Correct 1 ms 2392 KB Output is correct
4 Incorrect 1 ms 2396 KB Output isn't correct
5 Correct 1 ms 2392 KB Output is correct
6 Correct 1 ms 2392 KB Output is correct
7 Correct 2 ms 2392 KB Output is correct
8 Correct 7 ms 2392 KB Output is correct
9 Correct 1 ms 2392 KB Output is correct
10 Incorrect 1 ms 2392 KB Output isn't correct
11 Incorrect 1 ms 2392 KB Output isn't correct
12 Incorrect 1 ms 2392 KB Output isn't correct
13 Incorrect 1 ms 2392 KB Output isn't correct
14 Incorrect 1 ms 2396 KB Output isn't correct
15 Incorrect 1 ms 2392 KB Output isn't correct
16 Incorrect 2 ms 2392 KB Output isn't correct
17 Incorrect 2 ms 2392 KB Output isn't correct
18 Incorrect 2 ms 2392 KB Output isn't correct
19 Incorrect 7 ms 2392 KB Output isn't correct
20 Incorrect 8 ms 2628 KB Output isn't correct