Submission #1141693

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141693		AliMark71	timeismoney (balkan11_timeismoney)	C++20	50 / 100	10 ms	1100 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<array<int, 3>>> adj;

pair<vec<pair<int, int>>, pair<long long, long long>> mst(int piv) {
    vec<pair<int, int>> tree; fill(vs.begin(), vs.end(), 0);
    
    long long sum_c = 0, sum_t = 0;
    auto cmp_maker = [](int i) -> function<bool(array<int, 4>, array<int, 4>)>{
        if (i == 4) {
            return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
                return ((long long) lhs[2] * lhs[3]) > ((long long) rhs[2] * rhs[3]);
            };
        } else if (i == 5) {
            return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
                return ((long long) lhs[2] * rhs[3]) > ((long long) lhs[3] * rhs[2]);
            };
        } else if (i == 6) {
            return [](array<int, 4> lhs, array<int, 4> rhs) -> bool {
                return ((long long) lhs[3] * rhs[2]) > ((long long) lhs[2] * rhs[3]);
            };
        }
        return [i](array<int, 4> lhs, array<int, 4> rhs) -> bool {
            return lhs[i] > rhs[i];
        };
    };
    
    priority_queue<
        array<int, 4>,
        vec<array<int, 4>>,
        decltype(cmp_maker(piv))
    > q(cmp_maker(piv)); q.push({0, -1, 0, 0});
    
    while (!q.empty()) {
        auto [u, v, _c, _t] = q.top(); q.pop();
        if (vs[u]) continue;
        vs[u] = 1; if (0 <= u && 0 <= v) tree.push_back({u, v});
        sum_c += _c; sum_t += _t;
        
        for (auto [c, c_c, c_t] : adj[u]) if (!vs[c]) {
            q.push({c, u, c_c, c_t});
        }
    }
    
    return {tree, {sum_c, sum_t}};
}

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, d;
        cin>>a>>b>>c>>d;
        adj[a].push_back({b, c, d});
        adj[b].push_back({a, c, d});
    }
    
    pair<vec<pair<int, int>>, pair<int, int>> ans[] = {
        mst(2),
        mst(3),
        mst(4),
        mst(5),
        mst(6)
    };
    
    int a = 0;
    for (int i = 1; i < 5; i++) {
        if (ans[i].second.first * ans[i].second.second < ans[a].second.first * ans[a].second.second) {
            a = i;
        }
    }
    
    cout<<ans[a].second.first<<" "<<ans[a].second.second<<endl;
    for (auto [u, v] : ans[a].first) cout<<u<<" "<<v<<endl;
}

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

• Subtask 1: 50 / 100