Submission #1009352

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

timeismoney

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

const int MAXN=200, MAXM=10000;

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


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

    return false;
}

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

    return false;
}

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

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

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

    return;
}

void makehull(vector<int> left, vector<int> right, int xl, int yl, int xr, int yr)
{
    double m=(double)((double)yl-yr)/(xl-xr);
    vector<pair<double, int> > edges;
    //cout << xl << ' ' << yl << ' ' << xr << ' ' << yr << '\n';
    //cout << m << '\n';
    for (int i=0; i<n-1; i++)
    {
        int t=te[left[i]];
        int c=ce[left[i]];
        edges.push_back({-m*t+c, left[i]});
    }
    for (int i=0; i<n-1; i++)
    {
        int t=te[right[i]];
        int c=ce[right[i]];
        edges.push_back({-m*t+c, right[i]});
    }
    sort(edges.begin(), edges.end());
    for (int i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<int> mid;
    long long tsum=0, csum=0;
    for (int i=0; i<(int)edges.size(); i++)
    {
        int x=xe[edges[i].second];
        int y=ye[edges[i].second];
        int t=te[edges[i].second];
        int 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 (int i=0; i<m; i++)
        cin >> xe[i] >> ye[i] >> te[i] >> ce[i];
    int sorted[m];
    for (int i=0; i<m; i++)
        sorted[i]=i;
    long long tsum=0, csum=0;
    sort(sorted, sorted+m, tcompare);
    for (int i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<int> tmin;
    for (int i=0; i<m; i++)
    {
        int x=xe[sorted[i]];
        int y=ye[sorted[i]];
        int t=te[sorted[i]];
        int 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;
    }
    int ttemp=tsum;
    int ctemp=csum;
    for (int i=0; i<m; i++)
        sorted[i]=i;
    sort(sorted, sorted+m, ccompare);
    for (int i=0; i<n; i++)
    {
        link[i]=i;
        csize[i]=1;
    }
    vector<int> cmin;
    tsum=0;
    csum=0;
    for (int i=0; i<m; i++)
    {
        int x=xe[sorted[i]];
        int y=ye[sorted[i]];
        int t=te[sorted[i]];
        int 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 (int i=0; i<n-1; i++)
    {
        int x=xe[bestedges[i]];
        int y=ye[bestedges[i]];
        cout << x << ' ' << y << '\n';
    }

    return 0;
}

• Subtask 1: 60 / 100