Submission #39767

#	Time	Username	Problem	Language	Result	Execution time	Memory
39767		krauch	timeismoney (balkan11_timeismoney)	C++14	40 / 100	12 ms	3952 KiB

timeismoney

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef pair < int, int > PII;

#define forn(x, a, b) for (int x = a; x <= b; ++x)
#define for1(x, a, b) for (int x = a; x >= b; --x)
#define F first
#define S second
#define mkp make_pair
#define eb emplace_back
#define sz(a) (int)a.size();
#define all(a) a.begin(), a.end()

const int N = 2e5 + 6;

int n, m, ans, p[N], r[N];
vector < pair < int, PII > > vec;
vector < PII > ansvec;

int getp(int v) {
    return (p[v] == v ? v : getp(p[v]));
}

void unite(int v, int u) {
    v = getp(v), u = getp(u);
    if (r[v] == r[u]) r[v]++;
    if (r[v] > r[u]) p[u] = v;
    else p[v] = u;
}

int main() {

    cin >> n >> m;
    forn(i, 1, m) {
        int x, y, t, c;
        cin >> x >> y >> t >> c;
        vec.eb(c, PII(x, y));
    }

    forn(i, 1, n) p[i] = i;

    sort(all(vec));

    for (auto it : vec) {
        if (getp(it.S.F) == getp(it.S.S)) continue;
        unite(it.S.F, it.S.S);
        ans += it.F;
        ansvec.eb(it.S);
    }

    cout << ans << " " << ans << "\n";

    for (auto it : ansvec) cout << it.F << " " << it.S << "\n";

    return 0;
}

• Subtask 1: 40 / 100