#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
#define fi first
#define se second
#define For(i, l, r) for (auto i = (l); i < (r); i++)
#define ForE(i, l, r) for (auto i = (l); i <= (r); i++)
#define FordE(i, l, r) for (auto i = (l); i >= (r); i--)
#define Fora(v, a) for (auto v: (a))
#define bend(a) (a).begin(), (a).end()
#define isz(a) ((signed)(a).size())
using ll = long long;
using ld = long double;
using pii = pair <int, int>;
using vi = vector <int>;
using vpii = vector <pii>;
using vvi = vector <vi>;
template<bool Enable_small_to_large = true>
struct disjoint_set{
int n, _classes;
vector<int> p;
disjoint_set(int n): n(n), _classes(n), p(n, -1){ }
int make_set(){
p.push_back(-1);
++ _classes;
return n ++;
}
int classes() const{
return _classes;
}
int root(int u){
return p[u] < 0 ? u : p[u] = root(p[u]);
}
bool share(int a, int b){
return root(a) == root(b);
}
int size(int u){
return -p[root(u)];
}
bool merge(int u, int v){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v);
p[u] += p[v], p[v] = u;
return true;
}
bool merge(int u, int v, auto act){
u = root(u), v = root(v);
if(u == v) return false;
-- _classes;
bool swapped = false;
if constexpr(Enable_small_to_large) if(p[u] > p[v]) swap(u, v), swapped = true;
p[u] += p[v], p[v] = u;
act(u, v, swapped);
return true;
}
void clear(){
_classes = n;
fill(p.begin(), p.end(), -1);
}
vector<vector<int>> group_up(){
vector<vector<int>> g(n);
for(auto i = 0; i < n; ++ i) g[root(i)].push_back(i);
g.erase(remove_if(g.begin(), g.end(), [&](auto &s){ return s.empty(); }), g.end());
return g;
}
};
struct edge{
int u, v, x, y;
};
ll eval(const pair <pii, vpii>& ans){
return (ll)ans.fi.fi * ans.fi.se;
}
const int inf = 1e9 + 7;
int n, m;
vector <edge> a;
disjoint_set dsu(n);
pair <pii, vpii> ans = {pair{inf, inf}, vpii{}};
pair <pii, vpii> find_mst(int cx, int cy){
sort(bend(a), [&](const edge& lhs, const edge& rhs){
return lhs.x * cx + lhs.y * cy < rhs.x * cx + rhs.y * cy;
});
pair <pii, vpii> tans = {pair{0, 0}, vpii{}};
dsu.clear();
for (auto &[u, v, x, y]: a){
if (dsu.merge(u, v)){
tans.fi.fi += x; tans.fi.se += y;
tans.se.emplace_back(u, v);
}
}
if (eval(ans) > eval(tans)){
ans = tans;
}
return tans;
}
void recurse(const pii& p1, const pii& p2){
pii slope = {p2.se - p1.se, p2.fi - p1.fi};
pii p3 = find_mst(-slope.fi, slope.se).fi;
if (p3 == p1 or p3 == p2){
return;
}
pii slope2 = {p2.se - p3.se, p2.fi - p3.fi};
if ((ll)slope.fi * slope2.se == (ll)slope2.fi * slope.se){
return;
}
recurse(p1, p3);
recurse(p3, p2);
}
signed main(){
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("timeismoney.in", "r", stdin);
// freopen("timeismoney.out", "w", stdout);
cin >> n >> m;
For(i, 0, m){
int u, v, x, y; cin >> u >> v >> x >> y;
a.emplace_back(edge{u, v, x, y});
}
dsu = disjoint_set(n);
pii p1 = find_mst(1, 0).fi;
pii p2 = find_mst(0, 1).fi;
recurse(p1, p2);
cout << ans.fi.fi << ' ' << ans.fi.se << endl;
for (auto &[u, v]: ans.se){
cout << u << ' ' << v << endl;
}
}
/*
==================================================+
INPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
OUTPUT |
--------------------------------------------------|
--------------------------------------------------|
==================================================+
*/
Compilation message
timeismoney.cpp:51:30: warning: use of 'auto' in parameter declaration only available with '-fconcepts-ts'
51 | bool merge(int u, int v, auto act){
| ^~~~
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
1 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 |
212 KB |
Output is correct |
| 6 |
Correct |
0 ms |
212 KB |
Output is correct |
| 7 |
Correct |
1 ms |
340 KB |
Output is correct |
| 8 |
Correct |
3 ms |
600 KB |
Output is correct |
| 9 |
Correct |
0 ms |
212 KB |
Output is correct |
| 10 |
Correct |
0 ms |
212 KB |
Output is correct |
| 11 |
Correct |
0 ms |
212 KB |
Output is correct |
| 12 |
Correct |
1 ms |
212 KB |
Output is correct |
| 13 |
Correct |
0 ms |
212 KB |
Output is correct |
| 14 |
Correct |
3 ms |
212 KB |
Output is correct |
| 15 |
Correct |
2 ms |
212 KB |
Output is correct |
| 16 |
Correct |
38 ms |
340 KB |
Output is correct |
| 17 |
Correct |
40 ms |
340 KB |
Output is correct |
| 18 |
Correct |
38 ms |
360 KB |
Output is correct |
| 19 |
Correct |
342 ms |
600 KB |
Output is correct |
| 20 |
Correct |
339 ms |
600 KB |
Output is correct |
