oj.uz

Submission #49627

# Submission time Handle Problem Language Result Execution time Memory
49627 2018-06-01T07:25:24 Z Alexa2001 timeismoney (balkan11_timeismoney) C++17
75 / 100
 2000 ms 2444 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 (ll) c * A + (ll) d * B < (ll) other.c * A + (ll) 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]);
}

void unite(int x, int y)
{
    x = boss(x), y = boss(y);
    t[x] = y;
}

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;
            unite(a[i].x, 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;
            unite(a[i].x, 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 3 ms 504 KB Output is correct
2 Correct 2 ms 628 KB Output is correct
3 Correct 3 ms 628 KB Output is correct
4 Correct 2 ms 628 KB Output is correct
5 Correct 2 ms 680 KB Output is correct
6 Correct 2 ms 688 KB Output is correct
7 Correct 4 ms 788 KB Output is correct
8 Correct 9 ms 1028 KB Output is correct
9 Correct 3 ms 1028 KB Output is correct
10 Correct 0 ms 1028 KB Output is correct
11 Correct 2 ms 1064 KB Output is correct
12 Correct 2 ms 1064 KB Output is correct
13 Correct 2 ms 1064 KB Output is correct
14 Correct 7 ms 1064 KB Output is correct
15 Correct 6 ms 1088 KB Output is correct
16 Execution timed out 2062 ms 2436 KB Time limit exceeded
17 Execution timed out 2060 ms 2444 KB Time limit exceeded
18 Execution timed out 2076 ms 2444 KB Time limit exceeded
19 Execution timed out 2058 ms 2444 KB Time limit exceeded
20 Execution timed out 2060 ms 2444 KB Time limit exceeded