Submission #1302887

#	Time	Username	Problem	Language	Result	Execution time	Memory
1302887		vlomaczk	시간이 돈 (balkan11_timeismoney)	C++20	55 / 100	407 ms	1084 KiB

timeismoney

#include <bits/stdc++.h>
#include <ext/pb_ds/assoc_container.hpp>
#include <ext/pb_ds/tree_policy.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef __uint128_t lll;

template <typename T>
using ordered_set = tree<T, null_type, less<T>, rb_tree_tag, tree_order_statistics_node_update>;

struct Edge {
    ll a, b, t, m;
};

int n;
vector<Edge> edges;
vector<ll> rep, sajz;

ll Find(ll v) {
    return (rep[v] == v ? v : rep[v] = Find(rep[v]));
}

bool Union(ll a, ll b) {
    a = Find(a);
    b = Find(b);
    if (a == b) return 0;
    if (sajz[b] > sajz[a]) swap(a, b);
    rep[b] = a;
    sajz[a] += sajz[b];
    return 1;
}

vector<Edge> res;

/*  ---- MST ----
    liczenia na lll
    wynik wraca jako ll (do IO)
*/
pair<ll, ll> mst(ll wsp1, ll wsp2) {
    res.clear();
    for (ll i = 0; i < n; ++i) rep[i] = i, sajz[i] = 1;

    lll czas = 0;
    lll money = 0;

    sort(edges.begin(), edges.end(), [&](const Edge& x, const Edge& y) {
        lll v1 = (lll)wsp1 * x.t + (lll)wsp2 * x.m;
        lll v2 = (lll)wsp1 * y.t + (lll)wsp2 * y.m;
        return v1 < v2;
    });

    for (auto [a, b, t, m] : edges) {
        if (Union(a, b)) {
            czas += t;
            money += m;
            res.push_back({a, b, t, m});
        }
    }

    return { (ll)czas, (ll)money };
}

/* iloczyn t*m może wyjść poza ll */
vector<pair<lll, pair<ll, ll>>> odp;

void rek(ll x1, ll y1, ll x2, ll y2) {
    ll a = y2 - y1;
    ll b = x1 - x2;
    ll g = gcd(a, b);
    a /= g;
    b /= g;

    auto [t, m] = mst(a, b);
    odp.push_back({ (lll)t * m, {a, b} });

    if ((t == x1 && m == y1) ||
        (t == x2 && m == y2) ||
        ((lll)a * t + (lll)b * m == (lll)a * x1 + (lll)b * y1))
        return;

    rek(x1, y1, t, m);
    rek(t, m, x2, y2);
}

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);

    ll e;
    cin >> n >> e;

    for (ll i = 0; i < e; ++i) {
        ll a, b, t, m;
        cin >> a >> b >> t >> m;
        edges.push_back({a, b, t, m});
    }

    rep.assign(n, 0);
    sajz.assign(n, 0);

    auto [t1, m1] = mst(0, 1);
    auto [t2, m2] = mst(1, 0);

    rek(t1, m1, t2, m2);

    odp.push_back({ (lll)t1 * m1, {0, 1} });
    odp.push_back({ (lll)t2 * m2, {1, 0} });

    lll INF = (lll)4e18 * 4e18;
    pair<lll, pair<ll, ll>> ans = {INF, {0, 0}};

    for (auto &x : odp)
        ans = min(ans, x);

    auto [_, para] = ans;
    auto [a, b] = para;

    auto [t, m] = mst(a, b);

    cout << t << " " << m << "\n";
    for (auto [x, y, _, __] : res)
        cout << x << " " << y << "\n";

    return 0;
}

• Subtask 1: 55 / 100