제출 #1142246

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1142246		AliMark71	시간이 돈 (balkan11_timeismoney)	C++20	45 / 100	2099 ms	131072 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;

typedef vec<pair<int, int>> mst_t;
typedef pair<long long, long long> cost_time_t;
typedef pair<mst_t, cost_time_t> mst_res_t;

vec<function<bool(array<int, 4>, array<int, 4>)>> call_backs;

vec<bool> vs;
vec<vec<array<int, 3>>> adj;

mst_res_t mst(int piv, long long a = -1, long long b = -1, bool construct = false) {
    mst_t tree; fill(vs.begin(), vs.end(), 0);
    
    long long sum_c = 0, sum_t = 0;
    auto cmp_maker = [](int i, long long a = -1, long long b = -1) -> function<bool(array<int, 4>, array<int, 4>)>{
        if (i == 1 || i == 2) {
            return [i](array<int, 4> lhs, array<int, 4> rhs) -> bool {
                return lhs[i + 1] > rhs[i + 1];
            };
        } else {
            return [a, b](array<int, 4> lhs, array<int, 4> rhs) -> bool {
                return a * lhs[2] + b * lhs[3] > a * rhs[2] + b * rhs[3];
            };
        }
    };
    
    priority_queue<
        array<int, 4>,
        vec<array<int, 4>>,
        decltype(cmp_maker(piv, a, b))
    > q(cmp_maker(piv, a, b)); 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 (construct && 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}};
}

typedef pair<cost_time_t, pair<int, int>> cnvx_t;
cnvx_t cnvx(cnvx_t a, cnvx_t b) {
    auto min_p = [](cnvx_t a, cnvx_t b) {
        if (a.first.first * a.first.second <= b.first.first * b.first.second) return a;
        return b;
    };
    
    cnvx_t p = {
        mst(3, a.first.second - a.first.first, b.first.first - b.first.second).second,
        { a.first.second - a.first.first, b.first.first - b.first.second }
    };
    if (p == a || p == b) return min_p(a, b);
    
    return min_p(cnvx(a, p), cnvx(p, b));
}

void solve() {
    int n, m;
    cin>>n>>m; vs.resize(n); adj.resize(n);
    
    
    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});
    }
    
    
    auto c_point = mst(1).second;
    auto t_point = mst(2).second;
    
    auto opt_point = cnvx({
        c_point, { -1, -1 }
    }, {
        t_point, { -1, -1 }
    });
    
    cout<<opt_point.first.first<<" "<<opt_point.first.second<<endl;
    
    if (opt_point.second.first == -1) {
        if (c_point.first * c_point.second <= t_point.first * t_point.second)
            for (auto [u, v] : mst(1, -1, -1, true).first) cout<<u<<" "<<v<<endl;
        else
            for (auto [u, v] : mst(2, -1, -1, true).first) cout<<u<<" "<<v<<endl;
    } else {
        for (auto [u, v] : mst(3, opt_point.second.first, opt_point.second.second, true).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: 45 / 100