Submission #1141669

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141669		mohyay	timeismoney (balkan11_timeismoney)	C++20	40 / 100	7 ms	1096 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<ll,pair<ll,ll>>, vector<pair<ll,pair<ll,ll>>>, greater<pair<ll,pair<ll,ll>>>> pq;
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<n; i++) dsu[i] = i;
    for (int i=0; i<m; i++) {
        ll a, b, x, y; cin>>a>>b>>x>>y;
        v[a].pb({b, x, y});
        pq.push({x, {a, b}});
    }
    ll total = 0;
    vector<pair<ll,ll>> ans;
    while (!pq.empty()) {
        pair<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;
    }
    cout << total << " " << total << endl;
    for (auto [i, j] : ans) cout << i SP j << endl;
}

• Subtask 1: 40 / 100