Submission #845249

#	Time	Username	Problem	Language	Result	Execution time	Memory
845249		alexdd	timeismoney (balkan11_timeismoney)	C++17	30 / 100	2089 ms	600 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<pair<int,int>,pair<int,int>> edges[10005];
double cst;
bool caz;
int father[300];
int siz[300];
int gas(int x)
{
    if(x!=father[x])
        father[x]=gas(father[x]);
    return father[x];
}
void unite(int x, int y)
{
    x = gas(x);
    y = gas(y);
    if(x==y)
        return;
    if(siz[x]<siz[y])
        swap(x,y);
    father[y]=x;
    siz[x]+=siz[y];
}
double calc(pair<pair<int,int>,pair<int,int>> x)
{
    if(caz) return (double)x.first.first * cst + (double)x.first.second;
    else return (double)x.first.first + (double)x.first.second * cst;
}
bool cmp(pair<pair<int,int>,pair<int,int>> x, pair<pair<int,int>,pair<int,int>> y)
{
    return calc(x) < calc(y);
}
int best0,best1;
vector<pair<int,int>> sol;
vector<pair<int,int>> cur;
long long solve(double x)
{
    cst = x;
    cur.clear();
    sort(edges,edges+m,cmp);
    int sum0=0,sum1=0;
    for(int i=0;i<n;i++)
        father[i]=i,siz[i]=1;
    for(int i=0;i<m;i++)
    {
        if(gas(edges[i].second.first)!=gas(edges[i].second.second))
        {
            unite(edges[i].second.first,edges[i].second.second);
            cur.push_back(edges[i].second);
            sum0+=edges[i].first.first;
            sum1+=edges[i].first.second;
        }
    }
    if(best0==-1 || 1LL*sum0*sum1 < 1LL*best0*best1)
    {
        sol = cur;
        best0=sum0;
        best1=sum1;
    }
    return best0*best1;
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<m;i++)
    {
        cin>>edges[i].second.first>>edges[i].second.second>>edges[i].first.first>>edges[i].first.second;
    }
    double st,dr,mij1,mij2;
    best0=-1;

    for(int x=1;x<=2600000;x+=5000)///it1
    {
        caz=1;
        st = x;
        dr = x+999;
        for(int i=0;i<100;i++)///it2
        {
            mij1=st+(dr-st)/3;
            mij2=mij1+(dr-st)/3;
            if(solve(mij1)<solve(mij2))
                dr=mij2;
            else
                st=mij1;
        }
        caz=0;
        st = x;
        dr = x+999;
        for(int i=0;i<100;i++)
        {
            mij1=st+(dr-st)/3;
            mij2=mij1+(dr-st)/3;
            if(solve(mij1)<solve(mij2))
                dr=mij2;
            else
                st=mij1;
        }
    }
    cout<<best0<<" "<<best1<<"\n";
    for(int i=0;i<sol.size();i++)
        cout<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}
/**

it1 * it2 <= 10000

*/

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:104:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  104 |     for(int i=0;i<sol.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 30 / 100