Submission #678962

#	Time	Username	Problem	Language	Result	Execution time	Memory
678962		vjudge1	timeismoney (balkan11_timeismoney)	C++17	40 / 100	2098 ms	65536 KiB

timeismoney

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

typedef complex<long long> point;
const long long INF = (long long)1e18;

long long dot(point a, point b) {
    return (conj(a) * b).real();
}
long long cross(point a, point b) {
    return (conj(a) * b).imag();
}

struct DSU {
    vector<int> f;
    DSU(int n) : f(n) { iota(f.begin(), f.end(), 0); }
    int leader(int x) {
        while (x != f[x]) {
            x = f[x] = f[f[x]];
        }
        return x;
    }
    bool unionize(int x, int y) {
        x = leader(x);
        y = leader(y);
        if (x == y) {
            return false;
        }
        f[y] = x;
        return true;
    }
};

int n, m;
vector<array<long long, 5>> edges0;

point f(point axis) { // find mst on axis
    vector<array<long long, 5>> edges = edges0;
    for (int i = 0; i < m; i++) {
        edges[i][4] = dot(axis, point(edges[i][2], edges[i][3]));
    }

    sort(edges.begin(), edges.end(), [&](auto x, auto y) {
        return x[4] < y[4];
    });

    point res(0, 0);
    DSU dsu(n);

    for (auto [u, v, a, b, w] : edges) {
        if (dsu.unionize(u, v)) {
            res += point(a, b);
        }
    }
    return res;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n >> m;
    edges0.resize(m);
    for (int i = 0; i < m; i++) {
        int u, v, a, b;
        cin >> u >> v >> a >> b;
        edges0[i] = {u, v, a, b, 0};
    }

    point l(1, 0);
    point r(0, 1);

    vector<point> S;

    function<void(point, point)> divide = [&](point lp, point rp) {
//        cout << lp << " " << rp << '\n';
        point mid = (lp + rp);
        point mp = f(mid);
        if (mp == rp || mp == lp) {
//            cout << mp << '\n';
            S.push_back(lp);
            S.push_back(rp);
            return;
        }
        divide(lp, mp);
        divide(mp, rp);
    };
    divide(f(point(1, 0)), f(point(0, 1)));

    long long mn = INF;
    point key;
    for (auto p : S) {
        long long prod = p.real() * p.imag();
        if (prod < mn) {
            key = p;
            mn = prod;
        }
    }

    cout << key.real() << " " << key.imag() << "\n";

    vector<array<long long, 5>> edges = edges0;
    for (int i = 0; i < m; i++) {
        edges[i][4] = dot(key, point(edges[i][2], edges[i][3]));
    }

    sort(edges.begin(), edges.end(), [&](auto x, auto y) {
        return x[4] < y[4];
    });

    DSU dsu(n);

    for (auto [u, v, a, b, w] : edges) {
        if (dsu.unionize(u, v)) {
            cout << u << " " << v << "\n";
        }
    }
}

• Subtask 1: 40 / 100