oj.uz

답안 #1009352

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009352 2024-06-27T11:56:44 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
60 / 100
 91 ms 65536 KB 
#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.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 1 ms 344 KB Output is correct
3 Correct 1 ms 348 KB Output is correct
4 Correct 0 ms 348 KB Output is correct
5 Correct 1 ms 348 KB Output is correct
6 Correct 1 ms 344 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 4 ms 680 KB Output is correct
9 Correct 0 ms 344 KB Output is correct
10 Correct 0 ms 344 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Runtime error 91 ms 65536 KB Execution killed with signal 9
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 3 ms 344 KB Output isn't correct
15 Incorrect 4 ms 344 KB Output isn't correct
16 Incorrect 11 ms 604 KB Output isn't correct
17 Incorrect 14 ms 604 KB Output isn't correct
18 Incorrect 15 ms 600 KB Output isn't correct
19 Incorrect 15 ms 604 KB Output isn't correct
20 Incorrect 14 ms 604 KB Output isn't correct