Submission #1141840

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141840		mohyay	timeismoney (balkan11_timeismoney)	C++20	50 / 100	9 ms	1140 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
#define endl '\n'
using ll = long long;
#define pb push_back
#define pF first
#define pS second
#define SP <<' '<<
const ll mod = 1e9 + 7;
struct node {
    ll i, x, y;
};
vector<node> v[400];
ll dsu[112345];
priority_queue<pair<pair<ll,ll>,pair<ll,ll>>, vector<pair<pair<ll,ll>,pair<ll,ll>>>, greater<pair<pair<ll,ll>,pair<ll,ll>>>> pq;
priority_queue<pair<pair<ll,ll>,pair<ll,ll>>, vector<pair<pair<ll,ll>,pair<ll,ll>>>, greater<pair<pair<ll,ll>,pair<ll,ll>>>> pq1;
ll findboss(ll a) {
    if (dsu[a] == a) return a;
    return findboss(dsu[a]);
}
void merge(ll a, ll b) {
    a = findboss(a);
    b = findboss(b);
    dsu[a] = dsu[b];
}
int main() {
    //ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    ll n, m;cin>>n>>m;
    for (int i=0; i<m; i++) {
        ll a, b, x, y; cin>>a>>b>>x>>y;
        pq.push({{x, y}, {a, b}});
        swap(x, y);
        pq1.push({{x, y}, {a, b}});
    }
    ll total = 0, total1 = 0;
    vector<pair<ll,ll>> ans;
    for (int i=0; i<n; i++) dsu[i] = i;
    while (!pq.empty()) {
        pair<pair<ll,ll>,pair<ll,ll>> x = pq.top();
        pq.pop();
        ll i = x.pS.pF, j = x.pS.pS;
        if (findboss(i) == findboss(j)) continue;
        merge(x.pS.pF, x.pS.pS);
        ans.pb({x.pS.pF, x.pS.pS});
        total += x.pF.pF;
        total1 += x.pF.pS;
    }
    ll total2 = 0, total3 = 0;
    vector<pair<ll,ll>> ans1;
    for (int i=0; i<n; i++) dsu[i] = i;
    while (!pq1.empty()) {
        pair<pair<ll,ll>,pair<ll,ll>> x = pq1.top();
        pq1.pop();
        ll i = x.pS.pF, j = x.pS.pS;
        if (findboss(i) == findboss(j)) continue;
        merge(x.pS.pF, x.pS.pS);
        ans1.pb({x.pS.pF, x.pS.pS});
        total2 += x.pF.pF;
        total3 += x.pF.pS;
    }
    if (total * total1 <= total2 * total3) {
        cout << total << " " << total1 << endl;
        for (auto [i, j]: ans) cout << i SP j << endl;
    }
    else {
        cout << total2 << " " << total3 << endl;
        for (auto [i, j]: ans1) cout << i SP j << endl;
    }
}

• Subtask 1: 50 / 100