Submission #1009338

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1009338	2024-06-27T11:42:14 Z	vjudge1	timeismoney (balkan11_timeismoney)	C++17	60 / 100	86 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	1 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	460 KB	Output is correct
6	Correct	0 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	6 ms	604 KB	Output is correct
9	Correct	0 ms	348 KB	Output is correct
10	Correct	0 ms	344 KB	Output is correct
11	Correct	1 ms	344 KB	Output is correct
12	Runtime error	86 ms	65536 KB	Execution killed with signal 9
13	Correct	1 ms	348 KB	Output is correct
14	Incorrect	2 ms	348 KB	Output isn't correct
15	Incorrect	5 ms	568 KB	Output isn't correct
16	Incorrect	13 ms	604 KB	Output isn't correct
17	Incorrect	13 ms	608 KB	Output isn't correct
18	Incorrect	13 ms	616 KB	Output isn't correct
19	Incorrect	19 ms	756 KB	Output isn't correct
20	Incorrect	18 ms	604 KB	Output isn't correct