#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<array<point, 2>> S;
function<void(point, point)> divide = [&](point l, point r) {
if (lp == point(0, 0) || rp == point(0, 0)) {
return;
}
point lp = f(l);
point rp = f(r);
if (lp == rp) {
S.push_back({lp, l});
return;
}
point mid = (l + r);
mid /= 2;
if (cross(mid, l) == 0 || cross(mid, r) == 0) {
return;
}
point mp = f(mid);
divide(l, mid);
divide(mid, r);
};
divide(point(400, 0), point(0, 400));
long long mn = INF;
point ans;
point key;
for (auto [p, axis] : S) {
long long prod = p.real() * p.imag();
if (prod < mn) {
ans = p;
key = axis;
mn = prod;
}
}
ans *= -1;
cout << ans.real() << " " << ans.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";
}
}
}
Compilation message
timeismoney.cpp: In lambda function:
timeismoney.cpp:76:13: error: 'lp' was not declared in this scope; did you mean 'l'?
76 | if (lp == point(0, 0) || rp == point(0, 0)) {
| ^~
| l
timeismoney.cpp:76:34: error: 'rp' was not declared in this scope; did you mean 'r'?
76 | if (lp == point(0, 0) || rp == point(0, 0)) {
| ^~
| r
