Submission #1264171

#	Time	Username	Problem	Language	Result	Execution time	Memory
1264171		VMaksimoski008	timeismoney (balkan11_timeismoney)	C++20	95 / 100	298 ms	968 KiB

timeismoney

#include <bits/stdc++.h>
#define ar array
#define int long long

using namespace std;

using ll = long long;
using pii = pair<int, int>;
using pll = pair<ll, ll>;

const int mod = 1e9 + 7;
const ll inf = 1e9;
const int N = 1e5 + 5;

struct union_find {
    int n;
    vector<int> par, size;

    union_find(int _n) : n(_n), par(n+1), size(n+1, 1) {
        for(int i=1; i<=n; i++) par[i] = i;
    }

    int find(int u) {
        if(u == par[u]) return u;
        return par[u] = find(par[u]);
    }

    bool uni(int a, int b) {
        a = find(a); b = find(b);
        if(a == b) return 0;
        if(size[a] < size[b]) swap(a, b);
        size[a] += size[b];
        par[b] = a;
        return 1;
    }
};

struct point {
    ll x, y;
    bool operator<(const point &b) {
        return x * y < b.x * b.y;
    }
};

ll area(const point &a, const point &b, const point &c) {
    return (b.x - a.x) * (c.y - a.y) - (b.y - a.y) * (c.x - a.x);
}

int n, m;
vector<ar<int, 4> > edg;
vector<pii> used;

point mst(ll A, ll B) {
    ll T=0, C=0;
    union_find dsu(n);

    sort(edg.begin(), edg.end(), [&](const ar<int, 4> &x, const ar<int, 4> &y) {
        return A * x[2] + B * x[3] < A * y[2] + B * y[3]; 
    });

    used.clear();
    for(auto [a, b, t, c] : edg) {
        if(dsu.uni(a, b)) {
            T += t;
            C += c;
            used.push_back({ a, b });
        }
    }
    return { T, C };
}

signed main() {
    ios_base::sync_with_stdio(false);
    cout.tie(0); cin.tie(0);

    cin >> n >> m;
    while(m--) {
        int a, b, t, c;
        cin >> a >> b >> t >> c;
        edg.push_back({ a, b, t, c });
    }

    point ans = { inf, inf };
    vector<pii> to_print;
    point byT = mst(1, 0), byC = mst(0, 1);
    
    if(byT < ans) ans = byT, to_print = used;
    if(byC < ans) ans = byC, to_print = used;

    stack<pair<point, point> > st;
    st.push({ byT, byC });

    while(!st.empty()) {
        auto [tl, br] = st.top(); st.pop();

        point nxt = mst(-(br.y - tl.y), br.x - tl.x);
        if(nxt < ans) {
            ans = nxt;
            to_print = used;
        }

        if(area(tl, br, nxt) >= 0) continue;
        st.push({ tl, nxt });
        st.push({ nxt, br });
    }

    cout << ans.x << " " << ans.y << '\n';
    for(auto [a, b] : to_print)
        cout << a << " " << b << '\n';
}

• Subtask 1: 95 / 100