Submission #1141758

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141758		SulA	timeismoney (balkan11_timeismoney)	C++20	40 / 100	16 ms	584 KiB

timeismoney

#include <bits/stdc++.h>
#define all(a) a.begin(), a.end()
using namespace std;

const int timeCoef = 5, costCoef = 4;
struct DSU {
    vector<int> par;
    DSU(int n) : par(n) { iota(all(par), 0); }
    int find(int u) { return par[u] == u ? u : par[u] = find(par[u]); }
    bool merge(int u, int v) {
        u = find(u), v = find(v);
        if (u != v) par[v] = u;
        return u != v;
    }
};
signed main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int n,m; cin>>n>>m;
    int U[m], V[m], T[m], C[m];
    bool used[m];
    for (int i = 0; i < m; cin>>U[i]>>V[i]>>T[i]>>C[i++]);
    DSU dsu(n);
    int edges[m], sum1 = 0, sum2 = 0;
    vector<pair<int,int>> tree;
    iota(edges, edges + m, 0);
    sort(edges, edges + m, [&](int i, int j) { return timeCoef*T[i] + costCoef*C[i] < timeCoef*T[j] + costCoef*C[j]; });
    for (int iter = n-1; iter --> 0; ) {
        long long mn_val = 1e18;
        int mn_ind = -1;
        for (int i = 0; i < m; i++) {
            if (used[i]) continue;
            if (dsu.find(U[i]) == dsu.find(V[i])) continue;
            if ((sum1 + T[i])*(sum2 + C[i]) < mn_val) {
                mn_val = (sum1 + T[i])*(sum2 + C[i]);
                mn_ind = i;
            }
        }
        sum1 += T[mn_ind];
        sum2 += C[mn_ind];
        dsu.merge(U[mn_ind], V[mn_ind]);
        tree.emplace_back(U[mn_ind], V[mn_ind]);
    }
    cout<< sum1 << " " << sum2 << '\n';
    for (auto [u, v] : tree) cout<<u<<" "<<v<<"\n";
}

• Subtask 1: 40 / 100