Submission #1141656

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141656		AliMark71	timeismoney (balkan11_timeismoney)	C++20	40 / 100	3 ms	840 KiB

timeismoney

//
//  main.cpp
//  IntensiveCamp 1 2025
//
//  Created by Ali AlSalman on 24/01/2025.
//

#include <bits/stdc++.h>

template<typename T>
using vec = std::vector<T>;
using namespace std;

vec<bool> vs;
vec<vec<pair<int, int>>> adj;

void solve() {
    int n, m;
    cin>>n>>m; vs.resize(n); adj.resize(n);
    if (m == n - 1) {
        pair<int, int> arr[m];
        int s = 0, t = 0;
        while (m--) {
            int a, b, c, d;
            cin>>a>>b>>c>>d; s += c; t += d;
            arr[m] = {b, a};
        }
        
        cout<<s<<" "<<t<<endl;
        for (auto [a, b] : arr) cout<<a<<" "<<b<<endl;
        exit(0);
    }
    
    while (m--) {
        int a, b, c;
        cin>>a>>b>>c>>c;
        adj[a].push_back({b, c});
        adj[b].push_back({a, c});
    }
    
    auto cmp = [](array<int, 3> lhs, array<int, 3> rhs) { return lhs[0] > rhs[0]; };
    priority_queue<array<int, 3>, vec<array<int, 3>>, decltype(cmp)> q(cmp); q.push({0, 0, -1});
    
    int sum = 0;
    queue<pair<int, int>> ans;
    while (!q.empty()) {
        auto [d, u, v] = q.top(); q.pop();
        if (vs[u]) continue;
        vs[u] = 1; ans.push({u, v}); sum += d;
        for (auto [c, d] : adj[u]) if (!vs[c]) {
            q.push({d, c, u});
        }
    }
    
    cout<<sum<<" "<<sum<<endl;
    while (!ans.empty()) {
        if (ans.front().first < 0 || ans.front().second < 0) { ans.pop(); continue; }
        
        cout<<ans.front().first<<" "<<ans.front().second<<endl;
        ans.pop();
    }
}

int main() {
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
    
    
    int t = 1;
//    cin>>t;
    while (t--) solve();
}

• Subtask 1: 40 / 100