Submission #786999

#	Time	Username	Problem	Language	Result	Execution time	Memory
786999		vjudge1	timeismoney (balkan11_timeismoney)	C++17	100 / 100	342 ms	600 KiB

timeismoney

#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 (stderr)

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){
      |                              ^~~~

• Subtask 1: 100 / 100