Submission #491721

#	Time	Username	Problem	Language	Result	Execution time	Memory
491721		clams	timeismoney (balkan11_timeismoney)	C++17	100 / 100	82 ms	924 KiB

timeismoney

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using db = long double;

const int mxn = 205;
const int mxm = 10005;
const db MAX = 1e5;

struct Edge {
    ll a, b, t, c;
    db k;
    
    bool operator < (const Edge& oth) const {
        return k < oth.k;
    }    
};

int n, m, par[mxn], sz[mxn];
vector<Edge> v;

int fd(int u) {
    return par[u] = (par[u] == u ? u : fd(par[u]));    
}

bool unn(int u, int v) {
    u = fd(u);
    v = fd(v);
    if(u == v) return false;
    if(sz[u] < sz[v]) swap(u, v);
    sz[u] += sz[v];
    par[v] = u;
    return true;
}

void init(ll x) {
    iota(par, par + n, 0);
    fill(sz, sz + n, 1);
    for(auto& [a, b, t, c, k] : v)
        k = c * x + t * (MAX - x);
    sort(v.begin(), v.end());
}

ll solve(db mid) {
    init(mid);
    int solt = 0, solc = 0;
    for(auto [a, b, t, c, k] : v) {
        if(unn(a, b)) {
            solt += t;
            solc += c;
        }
    }
    return 1LL * solt * solc;
}

int main() {
    ios::sync_with_stdio(0); cin.tie(0);
    
    cin >> n >> m;
    v.resize(m);
    for(auto& [a, b, t, c, w] : v) cin >> a >> b >> t >> c;
        
    db l = 0, r = MAX;
    for(int ite = 0; ite < 70; ite++) {
        db m1 = (2 * l + r) / 3;
        db m2 = (l + 2 * r) / 3;
        if(solve(m1) < solve(m2)) r = m2;
        else l = m1;
    }
    
    init(l);
    vector<pair<int, int>> ans;
    int sumt = 0, sumc = 0;
    for(auto [A, B, t, c, k] : v) {
        if(unn(A, B)) {
            sumt += t;
            sumc += c;
            ans.push_back({A, B});
        }
    }
    
    cout << sumt << ' ' << sumc << '\n';
    for(auto [a, b] : ans) cout << a << ' ' << b << '\n';
}

// from: https://oj.uz/submission/482787

• Subtask 1: 100 / 100