Submission #845049

#	Time	Username	Problem	Language	Result	Execution time	Memory
845049		alexdd	timeismoney (balkan11_timeismoney)	C++17	5 / 100	656 ms	604 KiB

timeismoney

#include<bits/stdc++.h>
using namespace std;
int n,m;
pair<pair<int,int>,pair<int,int>> edges[10005];
pair<pair<int,int>,pair<int,int>> newe[10005];
vector<pair<pair<int,int>,pair<int,int>>> hull;

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];
}

int area(pair<int,int> a, pair<int,int> b, pair<int,int> c)
{
    return a.first * (b.second - c.second) + b.first * (c.second - a.second) + c.first * (a.second - b.second);
}
void get_hull()
{
    hull.clear();
    sort(edges,edges+m);
    for(int i=0;i<m;i++)
    {
        while(hull.size()>=2 && area(hull[hull.size()-2].first,hull[hull.size()-1].first,edges[i].first)<=0)
            hull.pop_back();
        hull.push_back(edges[i]);
    }
    int newm=0;
    for(int i=0;i<m;i++)
    {
        pair<pair<int,int>,pair<int,int>> x = *lower_bound(hull.begin(),hull.end(),edges[i]);
        if(x!=edges[i])
            newe[newm++]=edges[i];
    }
    m=newm;
    for(int i=0;i<m;i++)
        edges[i]=newe[i];
}
signed main()
{
    ios_base::sync_with_stdio(0);cin.tie(0);

    cin>>n>>m;
    for(int i=0;i<n;i++)
        father[i]=i,siz[i]=1;
    for(int i=0;i<m;i++)
    {
        cin>>edges[i].second.first>>edges[i].second.second>>edges[i].first.first>>edges[i].first.second;
    }
    int sum0=0,sum1=0;
    vector<pair<int,int>> sol;
    while(m>0)
    {
        get_hull();
        for(auto e:hull)
        {
            if(gas(e.second.first)!=gas(e.second.second))
            {
                unite(e.second.first,e.second.second);
                sol.push_back(e.second);
                sum0+=e.first.first;
                sum1+=e.first.second;
            }
        }
    }
    cout<<sum0<<" "<<sum1<<"\n";
    for(int i=0;i<sol.size();i++)
        cout<<sol[i].first<<" "<<sol[i].second<<"\n";
    return 0;
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:81: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]
   81 |     for(int i=0;i<sol.size();i++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 5 / 100