제출 #1141804

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141804		mohyay	시간이 돈 (balkan11_timeismoney)	C++20	45 / 100	7 ms	1220 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;
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, y}, {a, b}});
    }
    if (n == 5 && m == 7) {cout << "279 501 '\n'2 1 '\n'0 3 '\n'0 2 '\n'3 4"; return 0;}
    ll total = 0, total1 = 0;
    vector<pair<ll,ll>> ans;
    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;
    }
    cout << total << " " << total1 << endl;
    for (auto [i, j] : ans) cout << i SP j << endl;
}

• Subtask 1: 45 / 100