제출 #1141613

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1141613		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;

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++]);
    if (m == n-1) {
        cout << accumulate(T, T + m, 0) << " " << accumulate(C, C + m, 0) << '\n';
        for (int i = 0; i < m; i++) cout<<U[i]<<' '<<V[i]<<'\n';
    } else {
        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 T[i] + C[i] < T[j] + 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