Submission #1287098

#	Time	Username	Problem	Language	Result	Execution time	Memory
1287098		LIA	시간이 돈 (balkan11_timeismoney)	C++17	45 / 100	2095 ms	1508 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define vll vector<ll>

struct Dsu {
    vll p, sz;

    Dsu(ll n) : p(n), sz(n, 1) {
        iota(p.begin(), p.end(), 0);
    }

    ll find(ll v) {
        if (p[v] == v)
            return v;
        return p[v] = find(p[v]);
    }

    bool uni(ll a, ll b) {
        ll x = find(a), y = find(b);
        if (x == y)
            return 0;
        if (sz[x] < sz[y])
            swap(x, y);
        sz[x] += sz[y];
        p[y] = x;
        return 1;
    }
};

int main() {
    // if (!freopen("timeismoney.in", "r", stdin)) return 0;
    // if (!freopen("timeismoney.out", "w", stdout)) return 0;

    ll n, m;
    cin >> n >> m;
    vector<tuple<ll, ll, ll,ll> > vec, vec2;

    for (ll i = 0; i < m; ++i) {
        ll a, b, c, d;
        cin >> a >> b >> c >> d;
        vec.push_back({c, d, a, b});
    }

    sort(vec.begin(), vec.end());
    ll v = 1e18, cc, tt;
    vector<pair<ll, ll> > pairs, pairs2;
    for (auto [c,d, a, b]: vec) {
        Dsu dsu(n);
        ll c_cnt = 0, t_cnt = 0, used = 0;
        vec2.push_back({d, c, a, b});
        sort(vec2.begin(), vec2.end());
        for (auto [c,d,a,b]: vec2) {
            if (dsu.uni(a, b)) {
                used++;
                c_cnt += c;
                t_cnt += d;
                pairs.push_back({a, b});
            }
        }

        if ((used ==n-1) && (v > c_cnt * t_cnt)) {
            v = c_cnt * t_cnt;
            cc = c_cnt;
            tt = t_cnt;
            pairs2 = pairs;
        }

        pairs.clear();
    }
    cout << tt << " " <<cc << "\n";
    for (auto [a, b]: pairs2)
        cout << a << " " << b << "\n";
}

• Subtask 1: 45 / 100