oj.uz

Submission #268031

# Submission time Handle Problem Language Result Execution time Memory
268031 2020-08-16T08:00:32 Z stefantaga timeismoney (balkan11_timeismoney) C++14
50 / 100
 5 ms 512 KB 
#include <bits/stdc++.h>

using namespace std;
struct wow
{
    int x,y,bani,timp;
}v[10005];
bool compare (wow a,wow b)
{
    return a.bani+a.timp<b.bani+b.timp;
}
int tata[205],sol[2005],q,rang[205],sumbani,sumtimp;
int parinte (int x)
{
    if (tata[x]!=x)
    {
        return parinte(tata[x]);
    }
    return x;
}
void uneste (int x,int y)
{
    x=parinte(x);
    y=parinte(y);
    if (rang[x]<rang[y])
    {
        tata[x]=y;
    }
    else
    if (rang[x]>rang[y])
    {
        tata[y]=x;
    }
    else
    {
        tata[y]=x;
        rang[x]++;
    }
}
int n,m,i;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("timeismoney.in");
    ofstream cout("timeismoney.out");
    #endif // HOME
    cin>>n>>m;
    for (i=1;i<=m;i++)
    {
        cin>>v[i].x>>v[i].y>>v[i].bani>>v[i].timp;
    }
    sort (v+1,v+m+1,compare);
    for (i=1;i<=n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    for (i=1;i<=m;i++)
    {
        if (parinte(v[i].x)!=parinte(v[i].y))
        {
            uneste(v[i].x,v[i].y);
            sumbani=sumbani+v[i].bani;
            sumtimp=sumtimp+v[i].timp;
            sol[++q]=i;
        }
    }
    cout<<sumbani<<" "<<sumtimp<<'\n';
    for (i=1;i<=q;i++)
    {
        cout<<v[sol[i]].x<<" "<<v[sol[i]].y<<'\n';
    }
    return 0;
}

Subtask #1
50.0 / 100.0

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