oj.uz

답안 #49629

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
49629 2018-06-01T07:35:26 Z Alexa2001 시간이 돈 (balkan11_timeismoney) C++17
100 / 100
 600 ms 876 KB 
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int Nmax = 1e4 + 5;

int n, m, i, A, B, coef1, coef2, t[Nmax];
ll ans = LLONG_MAX;

struct edge
{
    int x, y, c, d;
    bool operator < (const edge &other) const
    {
        return c * A + d * B < other.c * A + other.d * B;
    }
} a[Nmax];

struct point
{
    int x, y;
    bool operator == (const point &other)
    {
        return x == other.x && y == other.y;
    }
};

inline ll parr(point A)
{
    return (ll) A.x * A.y;
}

int boss(int x)
{
    if(t[x] == x) return x;
    return t[x] = boss(t[x]);
}

point apm(int _A, int _B)
{
    A = _A, B = _B;
    sort(a+1, a+m+1);

    point ans = {0, 0};

    int i;
    for(i=0; i<n; ++i) t[i] = i;

    for(i=1; i<=m; ++i)
        if(boss(a[i].x) != boss(a[i].y))
        {
            ans.x += a[i].c;
            ans.y += a[i].d;
            t[t[a[i].x]] = t[a[i].y];
        }
    return ans;
}

void print_sol(int _A, int _B)
{
    A = _A, B = _B;
    sort(a+1, a+m+1);

    point ans = {0, 0};
    vector<point> v;

    int i;
    for(i=0; i<n; ++i) t[i] = i;

    for(i=1; i<=m; ++i)
        if(boss(a[i].x) != boss(a[i].y))
        {
            ans.x += a[i].c;
            ans.y += a[i].d;
            t[t[a[i].x]] = t[a[i].y];
            v.push_back({a[i].x, a[i].y});
        }

    cout << ans.x << ' ' << ans.y << '\n';
    for(auto e : v)
        cout << e.x << ' ' << e.y << '\n';
}

ll det(point A, point B, point C)
{
    return (ll) A.x * (B.y - C.y) + (ll) B.x * (C.y - A.y) + (ll) C.x * (A.y - B.y);
}

void solve(point A, point B)
{
    int p = A.y - B.y, q = B.x - A.x;
    point C = apm(p, q);

    if(!det(A, B, C)) return;

    if(parr(C) < ans)
        coef1 = p, coef2 = q, ans = parr(C);

    solve(A, C);
    solve(C, B);
}

int main()
{
 //   freopen("input", "r", stdin);
  //  freopen("output", "w", stdout);

    cin.sync_with_stdio(false);

    cin >> n >> m;
    for(i=1; i<=m; ++i)
        cin >> a[i].x >> a[i].y >> a[i].c >> a[i].d;

    point A = apm(1, 0);
    point B = apm(0, 1);

    if(parr(A) < ans)
        coef1 = 1, coef2 = 0, ans = parr(A);

    if(parr(B) < ans)
        coef1 = 0, coef2 = 1, ans = parr(B);

    if(A == B);
        else solve(A, B);

    print_sol(coef1, coef2);
    return 0;
}

Subtask #1
100.0 / 100.0

# 결과 실행 시간 메모리 Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 2 ms 408 KB Output is correct
4 Correct 2 ms 468 KB Output is correct
5 Correct 2 ms 468 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 4 ms 596 KB Output is correct
8 Correct 8 ms 672 KB Output is correct
9 Correct 3 ms 672 KB Output is correct
10 Correct 3 ms 672 KB Output is correct
11 Correct 2 ms 672 KB Output is correct
12 Correct 2 ms 672 KB Output is correct
13 Correct 2 ms 672 KB Output is correct
14 Correct 6 ms 672 KB Output is correct
15 Correct 6 ms 744 KB Output is correct
16 Correct 64 ms 744 KB Output is correct
17 Correct 68 ms 744 KB Output is correct
18 Correct 66 ms 744 KB Output is correct
19 Correct 547 ms 876 KB Output is correct
20 Correct 600 ms 876 KB Output is correct