Submission #1250988

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250988		matus192	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	385 ms	584 KiB

timeismoney

#include <bits/stdc++.h>

#include <ext/pb_ds/assoc_container.hpp>

using namespace std;
using namespace __gnu_pbds;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef tree<int, null_type, less<int>, rb_tree_tag, tree_order_statistics_node_update> oset;

#define REP(i, a, b) for (ll i = (a); i < (b); i++)
#define FOR(i, x) for (auto &i : x)
#define ff first
#define ss second
#define pb push_back
#define all(x) x.begin(), x.end()
#define IMAX INT_MAX
#define IMIN INT_MIN
#define LMAX LONG_LONG_MAX
#define LMIN LONG_LONG_MIN
#define MOD 1000000007
#define SIR 1000000009

ll n, m;
vector<pair<pll, pll>> E;
vll lnk, szs;
pair<pll, pll> ans;

ll find(ll a) {
    if (a == lnk[a]) return a;
    return lnk[a] = find(lnk[a]);
}

bool unite(ll a, ll b) {
    ll x = find(a);
    ll y = find(b);
    if (x == y) return false;
    if (szs[x] < szs[y]) swap(x, y);
    lnk[y] = x;
    szs[x] += szs[y];
    return true;
}

pll kostra(ll wa, ll wb, bool vypis = false) {
    ll res_a = 0, res_b = 0;
    lnk = vector<ll>(n);
    szs = vector<ll>(n, 1LL);
    for (ll i = 0; i < n; i++) lnk[i] = i;

    sort(all(E), [&](auto A, auto B) {
        ll r1 = wa * A.ff.ff + wb * A.ff.ss;
        ll r2 = wa * B.ff.ff + wb * B.ff.ss;
        if (r1 == r2) return A.ss < B.ss;
        return r1 < r2;
    });

    for (auto [cost, edge] : E) {
        if (unite(edge.ff, edge.ss)) {
            res_a += cost.ff;
            res_b += cost.ss;
            if (vypis == true) {
                cout << edge.ff << ' ' << edge.ss << '\n';
            }
        }
    }

    return {res_a, res_b};
}

void solve(pll a, pll b) {
    if (a == b) return;
    ll dy = llabs(a.ss - b.ss);
    ll dx = llabs(a.ff - b.ff);
    pll nw = kostra(dy, dx);
    if (nw == a || nw == b) return;
    if (nw.ff * nw.ss <
        ans.ss.ff * ans.ss.ss) {
        ans = {{dy, dx}, {nw.ff, nw.ss}};
    }
    solve(a, nw);
    solve(nw, b);
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cin >> n >> m;
    E = vector<pair<pll, pll>>(m);  // {cena1, cena2}, {u, v}
    for (ll i = 0; i < m; i++) {
        ll a, b, x, y;
        cin >> x >> y >> a >> b;
        E[i] = {{a, b}, {x, y}};
    }

    pll p1 = kostra(1, 0), p2 = kostra(0, 1);
    if (p1.ff * p1.ss > p2.ff * p2.ss) {
        ans = {{0, 1}, {p2.ff, p2.ss}};
    } else {
        ans = {{1, 0}, {p1.ff, p1.ss}};
    }
    solve(p1, p2);

    cout << ans.ss.ff << ' ' << ans.ss.ss << '\n';

    auto [wa, wb] = ans.ff;
    kostra(wa, wb, true);

    return 0;
}

• Subtask 1: 100 / 100