Submission #678980

#	Time	Username	Problem	Language	Result	Execution time	Memory
678980		vjudge1	timeismoney (balkan11_timeismoney)	C++17	50 / 100	2070 ms	1168 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();
}
long long area(point a, point b, point c) {
    return cross(b - a, c - a);
}

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};
    }

    vector<point> S;
    vector<point> T;

    function<void(point, point, point, point)> divide = [&](point lp, point rp, point l, point r) {
        point axis = point(rp.imag() - lp.imag(), lp.real() - rp.real());
        point mp = f(axis);
//        cout << lp << " " << rp << ":" << mp << '\n';
        if (area(lp, mp, rp) >= 0) {
            S.push_back(lp);
            T.push_back(l);
            S.push_back(rp);
            T.push_back(r);
            return;
        }
        divide(lp, mp, l, axis);
        divide(mp, rp, axis, r);
    };
    point l0(1, 0);
    point r0(0, 1);
    divide(f(l0), f(r0), l0, r0);

    long long mn = INF;
    point key;
    point dir;
    for (int i = 0; i < S.size(); i++) {
        point p = S[i];
        point t = T[i];
        long long prod = p.real() * p.imag();
        if (prod < mn) {
            key = p;
            dir = t;
            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(dir, 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";
        }
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:97:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::complex<long long int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |     for (int i = 0; i < S.size(); i++) {
      |                     ~~^~~~~~~~~~

• Subtask 1: 50 / 100