Submission #268119

#	Time	Username	Problem	Language	Result	Execution time	Memory
268119		stefantaga	timeismoney (balkan11_timeismoney)	C++14	100 / 100	476 ms	1272 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;
struct wow
{
    long double x,y,bani,timp,constanta;
}v[10005];
bool compare (wow a,wow b)
{
    return a.constanta<b.constanta;
}
int tata[205],sol[2005],q,rang[205],sumbani,sumtimp;
int n,m,i;
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]++;
    }
}
long double MAX=1e6;
int val(long double mij)
{
    int i;
    for (i=1;i<=m;i++)
    {
        v[i].constanta=v[i].timp*mij+v[i].bani*(MAX-mij);
    }
    sort (v+1,v+m+1,compare);
    for (i=1;i<=n;i++)
    {
        tata[i]=i;
        rang[i]=1;
    }
    q=0;
    sumbani=0;
    sumtimp=0;
    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;
        }
    }
    return sumbani*sumtimp;
}
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].timp>>v[i].bani;
        v[i].x++;
        v[i].y++;
    }
    long double st=1,dr=MAX-1;
    while (dr-st>=1e-6)
    {
        long double m1=st+(dr-st)/3;
        long double m2=dr-(dr-st)/3;
        if (val(m1)<val(m2))
        {
            dr=m2;
        }
        else
        {
            st=m1;
        }
    }
    val(st);
    cout<<sumtimp<<" "<<sumbani<<'\n';
    for (i=1;i<=q;i++)
    {
        cout<<v[sol[i]].x-1<<" "<<v[sol[i]].y-1<<'\n';
    }
    return 0;
}

• Subtask 1: 100 / 100