Submission #268119

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
268119	2020-08-16T08:57:47 Z	stefantaga	timeismoney (balkan11_timeismoney)	C++14	100 / 100	476 ms	1272 KB

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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	15 ms	384 KB	Output is correct
2	Correct	1 ms	384 KB	Output is correct
3	Correct	2 ms	384 KB	Output is correct
4	Correct	4 ms	384 KB	Output is correct
5	Correct	17 ms	384 KB	Output is correct
6	Correct	16 ms	384 KB	Output is correct
7	Correct	71 ms	512 KB	Output is correct
8	Correct	351 ms	1272 KB	Output is correct
9	Correct	1 ms	384 KB	Output is correct
10	Correct	2 ms	384 KB	Output is correct
11	Correct	2 ms	384 KB	Output is correct
12	Correct	4 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Correct	14 ms	384 KB	Output is correct
15	Correct	17 ms	440 KB	Output is correct
16	Correct	79 ms	512 KB	Output is correct
17	Correct	74 ms	512 KB	Output is correct
18	Correct	87 ms	512 KB	Output is correct
19	Correct	413 ms	1152 KB	Output is correct
20	Correct	476 ms	1180 KB	Output is correct