oj.uz

답안 #1009345

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
1009345 2024-06-27T11:49:16 Z vjudge1 시간이 돈 (balkan11_timeismoney) C++17
60 / 100
 89 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(m*tsum+csum-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 348 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 1 ms 348 KB Output is correct
7 Correct 1 ms 348 KB Output is correct
8 Correct 3 ms 652 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 432 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Runtime error 89 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 348 KB Output isn't correct
16 Incorrect 13 ms 604 KB Output isn't correct
17 Incorrect 13 ms 600 KB Output isn't correct
18 Incorrect 13 ms 632 KB Output isn't correct
19 Incorrect 16 ms 780 KB Output isn't correct
20 Incorrect 16 ms 604 KB Output isn't correct