Submission #268028

#	Time	Username	Problem	Language	Result	Execution time	Memory
268028		stefantaga	timeismoney (balkan11_timeismoney)	C++14	45 / 100	6 ms	512 KiB

timeismoney

#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: 45 / 100