oj.uz

Submission #49628

# Submission time Handle Problem Language Result Execution time Memory
49628 2018-06-01T07:31:18 Z Alexa2001 timeismoney (balkan11_timeismoney) C++17
75 / 100
 2000 ms 1944 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';
}

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

    if(C == A || C == B) 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
75.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 376 KB Output is correct
2 Correct 2 ms 376 KB Output is correct
3 Correct 3 ms 520 KB Output is correct
4 Correct 2 ms 520 KB Output is correct
5 Correct 3 ms 520 KB Output is correct
6 Correct 2 ms 520 KB Output is correct
7 Correct 3 ms 588 KB Output is correct
8 Correct 8 ms 652 KB Output is correct
9 Correct 3 ms 652 KB Output is correct
10 Correct 2 ms 652 KB Output is correct
11 Correct 2 ms 652 KB Output is correct
12 Correct 6 ms 652 KB Output is correct
13 Correct 2 ms 652 KB Output is correct
14 Correct 9 ms 652 KB Output is correct
15 Correct 5 ms 652 KB Output is correct
16 Execution timed out 2058 ms 1944 KB Time limit exceeded
17 Execution timed out 2061 ms 1944 KB Time limit exceeded
18 Execution timed out 2064 ms 1944 KB Time limit exceeded
19 Execution timed out 2077 ms 1944 KB Time limit exceeded
20 Execution timed out 2065 ms 1944 KB Time limit exceeded