Submission #1009357

#	Time	Username	Problem	Language	Result	Execution time	Memory
1009357		vjudge1	timeismoney (balkan11_timeismoney)	C++17	60 / 100	85 ms	65536 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

const long long MAXN=200, MAXM=10000;

long long n, m;
long long xe[MAXM], ye[MAXM], te[MAXM], ce[MAXM];
long long link[MAXN], csize[MAXN];
long long tbest=2e18, cbest=1;
vector<long long> bestedges;


bool tcompare(long long x, long long y)
{
    if (te[x]<te[y])
        return true;

    return false;
}

bool ccompare(long long x, long long y)
{
    if (ce[x]<ce[y])
        return true;

    return false;
}

long long find(long long x)
{
    if (link[x]==x)
        return x;

    return link[x]=find(link[x]);
}

void unite(long long x, long long y)
{
    if (csize[x]<csize[y])
        swap(x, y);
    csize[x]=csize[x]+csize[y];
    link[y]=x;

    return;
}

void makehull(vector<long long> left, vector<long long> right, long long xl, long long yl, long long xr, long long yr)
{
    double m=(double)((double)yl-yr)/(xl-xr);
    vector<pair<double, long long> > edges;
    //cout << xl << ' ' << yl << ' ' << xr << ' ' << yr << '\n';
    //cout << m << '\n';
    for (long long i=0; i<n-1; i++)
    {
        long long t=te[left[i]];
        long long c=ce[left[i]];
        edges.push_back({-m*t+c, left[i]});
    }
    for (long long i=0; i<n-1; i++)
    {
        long long t=te[right[i]];
        long long c=ce[right[i]];
        edges.push_back({-m*t+c, right[i]});
    }
    sort(edges.begin(), edges.end());
    for (long long i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<long long> mid;
    long long tsum=0, csum=0;
    for (long long i=0; i<(long long)edges.size(); i++)
    {
        long long x=xe[edges[i].second];
        long long y=ye[edges[i].second];
        long long t=te[edges[i].second];
        long long c=ce[edges[i].second];
        if (find(x)==find(y))
            continue;
        unite(find(x), find(y));
        mid.push_back(edges[i].second);
        tsum=tsum+t;
        csum=csum+c;
    }
    if (tsum*csum<tbest*cbest)
    {
        tbest=tsum;
        cbest=csum;
        bestedges=mid;
    }
    double k=(double)yl-m*xl;
    if (abs((double)csum-m*tsum-k)<(double)1e-9)
        return;
    sort(mid.begin(), mid.end());
    if (mid!=left && mid!=right)
    {
        makehull(left, mid, xl, yl, tsum, csum);
        makehull(mid, right, tsum, csum, xr, yr);
    }

    return;
}

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    cin >> n >> m;
    for (long long i=0; i<m; i++)
        cin >> xe[i] >> ye[i] >> te[i] >> ce[i];
    long long sorted[m];
    for (long long i=0; i<m; i++)
        sorted[i]=i;
    long long tsum=0, csum=0;
    sort(sorted, sorted+m, tcompare);
    for (long long i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<long long> tmin;
    for (long long i=0; i<m; i++)
    {
        long long x=xe[sorted[i]];
        long long y=ye[sorted[i]];
        long long t=te[sorted[i]];
        long long c=ce[sorted[i]];
        if (find(x)==find(y))
            continue;
        unite(find(x), find(y));
        tmin.push_back(sorted[i]);
        tsum=tsum+t;
        csum=csum+c;
    }
    if (tsum*csum<tbest*cbest)
    {
        tbest=tsum;
        cbest=csum;
        bestedges=tmin;
    }
    long long ttemp=tsum;
    long long ctemp=csum;
    for (long long i=0; i<m; i++)
        sorted[i]=i;
    sort(sorted, sorted+m, ccompare);
    for (long long i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<long long> cmin;
    tsum=0;
    csum=0;
    for (long long i=0; i<m; i++)
    {
        long long x=xe[sorted[i]];
        long long y=ye[sorted[i]];
        long long t=te[sorted[i]];
        long long c=ce[sorted[i]];
        if (find(x)==find(y))
            continue;
        unite(find(x), find(y));
        cmin.push_back(sorted[i]);
        tsum=tsum+t;
        csum=csum+c;
    }
    if (tsum*csum<tbest*cbest)
    {
        tbest=tsum;
        cbest=csum;
        bestedges=cmin;
    }
    makehull(tmin, cmin, ttemp, ctemp, tsum, csum);
    cout << tbest << ' ' << cbest << '\n';
    for (long long i=0; i<n-1; i++)
    {
        long long x=xe[bestedges[i]];
        long long y=ye[bestedges[i]];
        cout << x << ' ' << y << '\n';
    }

    return 0;
}

• Subtask 1: 60 / 100