제출 #1194811

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1194811		AliMark71	시간이 돈 (balkan11_timeismoney)	C++20	100 / 100	1892 ms	1640 KiB

timeismoney

//
//  main.cpp
//  GeneralCompetitiveProgramming
//
//  Created by Ali AlSalman on 12/07/2023.
//

#include <bits/stdc++.h>

//#define INTERACTIVE
//#define TESTCASES

#ifndef INTERACTIVE
#define endl '\n'
#endif

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

typedef vec<pair<int, int>> mst_t;
struct mst_value_t {
    long long cost, time;
    bool operator ==(const mst_value_t &other) const {
        return cost == other.cost && time == other.time;
    }
};
struct mst_query_t {
    mst_t mst;
    mst_value_t value;
};

bool mask = true;
vec<bool> vis;
vec<vec<array<int, 3>>> adj;

mst_query_t mst(long long a, long long b, bool construct = false) {
    mst_t tree;
    
    long long sum_c = 0, sum_t = 0;
    auto cmp_maker = [](long long a, long long b) -> function<bool(array<long long, 4>, array<long long, 4>)>{
        return [a, b](array<long long, 4> lhs, array<long long, 4> rhs) -> bool {
            return a * lhs[2] + b * lhs[3] > a * rhs[2] + b * rhs[3];
        };
    };
    
    priority_queue<
        array<long long, 4>,
        vec<array<long long, 4>>,
        decltype(cmp_maker(a, b))
    > q(cmp_maker(a, b)); q.push({0, -1, 0, 0});
    
    while (!q.empty()) {
        auto [u, v, _c, _t] = q.top(); q.pop();
        if (vis[u] == mask) continue;
        vis[u] = !vis[u]; 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 (vis[c] != mask) {
            q.push({c, u, c_c, c_t});
        }
    }
    
    mask = !mask;
    return {tree, {sum_c, sum_t}};
}

struct mst_producer_t {
    long long cost_factor, time_factor;
};
struct cnvx_t {
    mst_producer_t producer;
    mst_value_t mst_value;
};

cnvx_t cnvx(cnvx_t a, cnvx_t b) {
    auto min_p = [](cnvx_t a, cnvx_t b) {
        if (a.mst_value.cost * a.mst_value.time <= b.mst_value.cost * b.mst_value.time) return a;
        return b;
    };
    
    cnvx_t p = {
        { a.mst_value.time - b.mst_value.time, b.mst_value.cost - a.mst_value.cost },
        mst(a.mst_value.time - b.mst_value.time, b.mst_value.cost - a.mst_value.cost).value
    };
    if (p.mst_value == a.mst_value || p.mst_value == b.mst_value) return min_p(a, b);
    
    return min_p(cnvx(a, p), cnvx(p, b));
}

void solve() {
    int n, m;
    cin>>n>>m; vis.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, 0).value;
    auto t_point = mst(0, 1).value;
    
    auto opt = cnvx({
        { 1, 0 }, c_point
    }, {
        { 0, 1 }, t_point
    });
    
    cout<<opt.mst_value.cost<<" "<<opt.mst_value.time<<endl;
    
    for (auto [u, v] : mst(opt.producer.cost_factor, opt.producer.time_factor, true).mst) {
        cout<<u<<" "<<v<<endl;
    }
}

int main() {
#ifndef INTERACTIVE
    ios::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
#endif
    
    
    int t = 1;
#ifdef TESTCASES
    cin>>t;
#endif
    while (t--) solve();
}

• Subtask 1: 100 / 100