Submission #1009339

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1009339	2024-06-27T11:43:20 Z	vjudge1	timeismoney (balkan11_timeismoney)	C++17	60 / 100	88 ms	65536 KB

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

int k=0;

void makehull(vector<int> left, vector<int> right, int xl, int yl, int xr, int yr)
{
    k=k+1;
    //if (k>10)
      //  return;
    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;
    }
    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.0 / 100.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	344 KB	Output is correct
2	Correct	0 ms	348 KB	Output is correct
3	Correct	0 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	488 KB	Output is correct
8	Correct	3 ms	604 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	348 KB	Output is correct
11	Correct	0 ms	344 KB	Output is correct
12	Runtime error	88 ms	65536 KB	Execution killed with signal 9
13	Correct	1 ms	344 KB	Output is correct
14	Incorrect	3 ms	348 KB	Output isn't correct
15	Incorrect	5 ms	588 KB	Output isn't correct
16	Incorrect	12 ms	604 KB	Output isn't correct
17	Incorrect	13 ms	652 KB	Output isn't correct
18	Incorrect	13 ms	604 KB	Output isn't correct
19	Incorrect	19 ms	712 KB	Output isn't correct
20	Incorrect	16 ms	604 KB	Output isn't correct