Submission #49629

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
49629	2018-06-01T07:35:26 Z	Alexa2001	timeismoney (balkan11_timeismoney)	C++17	100 / 100	600 ms	876 KB

timeismoney

#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

#	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	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