oj.uz

Submission #678966

# Submission time Handle Problem Language Result Execution time Memory
678966 2023-01-07T04:54:47 Z vjudge1 timeismoney (balkan11_timeismoney) C++17
40 / 100
 11 ms 1080 KB 
#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;

    function<void(point, point)> divide = [&](point lp, point rp) {
        point mid = (lp + rp);
        point mp = f(mid);
//        cout << lp << " " << rp << ":" << mp << '\n';
        if (area(mp, lp, rp) <= 0) {
            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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 2 ms 468 KB Output is correct
8 Correct 10 ms 980 KB Output is correct
9 Incorrect 0 ms 212 KB Output isn't correct
10 Incorrect 1 ms 212 KB Output isn't correct
11 Incorrect 0 ms 212 KB Output isn't correct
12 Incorrect 1 ms 212 KB Output isn't correct
13 Incorrect 0 ms 212 KB Output isn't correct
14 Incorrect 1 ms 340 KB Output isn't correct
15 Incorrect 1 ms 212 KB Output isn't correct
16 Incorrect 2 ms 468 KB Output isn't correct
17 Incorrect 2 ms 468 KB Output isn't correct
18 Incorrect 2 ms 468 KB Output isn't correct
19 Incorrect 11 ms 1080 KB Output isn't correct
20 Incorrect 11 ms 980 KB Output isn't correct