Submission #482787

#	Time	Username	Problem	Language	Result	Execution time	Memory
482787		solarmagic	timeismoney (balkan11_timeismoney)	C++17	100 / 100	75 ms	776 KiB

timeismoney

#include <bits/stdc++.h>
#define all(x) begin(x), end(x)
using namespace std;
using db = long double;
using ll = long long;

db MAX = 1e5;

struct edge{
	ll a, b, t, c;
	db k;
};
 
ll n, m;
vector<edge> v;
vector<ll> p, sz;

ll find(ll x){
	if(x == p[x]) return x;
	return p[x] = find(p[x]);
}
 
void init(ll mid) {
    fill(all(sz), 1);
    iota(all(p), 0);
    for (auto& [a, b, t, c, k] : v) {
        k = c * mid + t * (MAX - mid);
    }
	sort(all(v), [](auto& a, auto& b){return a.k < b.k;});
}

ll solve(db mid){
    init(mid);

    ll solt = 0, solc = 0;
    for (auto [a, b, t, c, k] : v) {
        a = find(a), b = find(b);
        if (a == b) continue;
        solt += t;
        solc += c;
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
	}
	return solt * solc;
}

int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);

	cin >> n >> m;
	v.resize(m);
    p.resize(n);
    sz.resize(n);

    for (auto& [a, b, t, c, val] : v)
        cin >> a >> b >> t >> c;

	db l = 0, r = MAX;
	while(r - l > 1e-7) {
		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<ll,ll>> ans;
	ll sumt = 0, sumc = 0;
    for (auto [A, B, t, c, k] : v) {
        auto a = find(A), b = find(B);
        if (a == b) continue;
        sumt += t;
        sumc += c;
        ans.emplace_back(A, B);
        if(sz[a] < sz[b]) swap(a, b);
        sz[a] += sz[b];
        p[b] = a;
	}
    cout << sumt << ' ' << sumc << "\n";
    for (auto [a, b] : ans) {
        cout << a << ' ' << b << '\n';
    }
}

Compilation message (stderr)

timeismoney.cpp: In function 'int main()':
timeismoney.cpp:57:5: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
   57 |     for (auto& [a, b, t, c, val] : v)
      |     ^~~
timeismoney.cpp:60:2: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
   60 |  db l = 0, r = MAX;
      |  ^~

• Subtask 1: 100 / 100