Submission #43267

#	Time	Username	Problem	Language	Result	Execution time	Memory
43267		cheater2k	timeismoney (balkan11_timeismoney)	C++14	100 / 100	495 ms	852 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;

const int N = 220;
const int M = 10020;

int n, m;
int par[N];
int sz[N];
int best_a, best_b;
int res = 2e9;

struct Point {
    int x; int y;
    Point(int x = 0, int y = 0): x(x), y(y) {}
};

struct Edge {
    int u; int v; int x; int y;
} ed[M];
vector< pair<int,int> > vres;

int anc(int p) { return p == par[p] ? p : par[p] = anc(par[p]); }
void join(int p, int q) {
    if (sz[p] < sz[q]) par[p] = q, sz[q] += sz[p], sz[p] = 0;
    else par[q] = p, sz[p] += sz[q], sz[q] = 0;
}

Point getmst(int a, int b, bool trace = false) {
    sort(ed, ed + m, [&](Edge p, Edge q) {
        return a * p.x + b * p.y < a * q.x + b * q.y;
    });
    for (int i = 0; i < n; ++i) par[i] = i, sz[i] = 1;

    int resx = 0;
    int resy = 0;
    int need = n - 1;
    for (int i = 0; i < m; ++i) {
        int u = anc(ed[i].u), v = anc(ed[i].v);
        if (u == v) continue;

        --need;
        join(u, v);
        resx += ed[i].x;
        resy += ed[i].y;
        if (trace) {
            vres.push_back(make_pair(ed[i].u, ed[i].v));
        }
        if (!need) break;
    }

    if (res > 1LL * resx * resy) {
        best_a = a;
        best_b = b;
        res = 1LL * resx * resy;
    }

    if (trace) {
        printf("%d %d\n", resx, resy);
        for (auto &e : vres) {
            printf("%d %d\n", e.first, e.second);
        }
    }

    return Point(resx, resy);
}

long long ccw(Point O, Point A, Point B) {
    A.x -= O.x; A.y -= O.y;
    B.x -= O.x; B.y -= O.y;
    return 1LL * A.x * B.y - 1LL * A.y * B.x;
}

void solve(Point &p, Point &q) {
    res = min(res, p.x * p.y);
    res = min(res, q.x * q.y);

    int b = q.x - p.x; // >= 0
    int a = p.y - q.y; // >= 0
    Point mid = getmst(a, b);
    if (ccw(mid, q, p) <= 0) return;

    solve(p, mid);
    solve(mid, q);
}

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);

    cin >> n >> m;
    for (int i = 0; i < m; ++i) {
        cin >> ed[i].u >> ed[i].v >> ed[i].x >> ed[i].y;
    }

    Point p = getmst(1, 0); // x
    Point q = getmst(0, 1); // y
    solve(p, q);

    getmst(best_a, best_b, true);
}

• Subtask 1: 100 / 100