Submission #1141728

#	Time	Username	Problem	Language	Result	Execution time	Memory
1141728		SulA	timeismoney (balkan11_timeismoney)	C++20	50 / 100	2 ms	584 KiB

timeismoney

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

const int timeCoef = 190, costCoef = 147;
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];
    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 i : edges) {
        if (dsu.merge(U[i], V[i])) {
            sum1 += T[i];
            sum2 += C[i];
            tree.emplace_back(U[i], V[i]);
        }
    }
    cout<< sum1 << " " << sum2 << '\n';
    for (auto [u, v] : tree) cout<<u<<" "<<v<<"\n";
}

• Subtask 1: 50 / 100