#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(lp.imag() - rp.imag(), rp.real() - lp.real());
point mp = f(axis);
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
timeismoney.cpp: In function 'int main()':
timeismoney.cpp:96: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]
96 | for (int i = 0; i < S.size(); i++) {
| ~~^~~~~~~~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Runtime error |
1046 ms |
65536 KB |
Execution killed with signal 9 |
| 2 |
Runtime error |
104 ms |
65536 KB |
Execution killed with signal 9 |
| 3 |
Runtime error |
177 ms |
65536 KB |
Execution killed with signal 9 |
| 4 |
Runtime error |
420 ms |
65536 KB |
Execution killed with signal 9 |
| 5 |
Execution timed out |
2091 ms |
58520 KB |
Time limit exceeded |
| 6 |
Runtime error |
1860 ms |
65536 KB |
Execution killed with signal 9 |
| 7 |
Execution timed out |
2079 ms |
11316 KB |
Time limit exceeded |
| 8 |
Execution timed out |
2074 ms |
2748 KB |
Time limit exceeded |
| 9 |
Runtime error |
142 ms |
65536 KB |
Execution killed with signal 9 |
| 10 |
Runtime error |
279 ms |
65536 KB |
Execution killed with signal 9 |
| 11 |
Runtime error |
202 ms |
65536 KB |
Execution killed with signal 9 |
| 12 |
Runtime error |
534 ms |
65536 KB |
Execution killed with signal 9 |
| 13 |
Runtime error |
523 ms |
65536 KB |
Execution killed with signal 9 |
| 14 |
Execution timed out |
2080 ms |
38452 KB |
Time limit exceeded |
| 15 |
Execution timed out |
2088 ms |
53912 KB |
Time limit exceeded |
| 16 |
Execution timed out |
2088 ms |
4812 KB |
Time limit exceeded |
| 17 |
Execution timed out |
2090 ms |
4728 KB |
Time limit exceeded |
| 18 |
Execution timed out |
2080 ms |
4764 KB |
Time limit exceeded |
| 19 |
Execution timed out |
2094 ms |
1828 KB |
Time limit exceeded |
| 20 |
Execution timed out |
2083 ms |
1780 KB |
Time limit exceeded |
