oj.uz

Submission #39767

# Submission time Handle Problem Language Result Execution time Memory
39767 2018-01-18T10:14:35 Z krauch timeismoney (balkan11_timeismoney) C++14
40 / 100
 12 ms 3952 KB 
#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.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 3584 KB Output is correct
2 Correct 0 ms 3584 KB Output is correct
3 Correct 0 ms 3584 KB Output is correct
4 Correct 0 ms 3584 KB Output is correct
5 Correct 0 ms 3584 KB Output is correct
6 Correct 0 ms 3584 KB Output is correct
7 Correct 3 ms 3584 KB Output is correct
8 Correct 8 ms 3952 KB Output is correct
9 Incorrect 0 ms 3584 KB Output isn't correct
10 Incorrect 0 ms 3584 KB Output isn't correct
11 Incorrect 0 ms 3584 KB Output isn't correct
12 Incorrect 0 ms 3584 KB Output isn't correct
13 Incorrect 0 ms 3584 KB Output isn't correct
14 Incorrect 1 ms 3584 KB Output isn't correct
15 Incorrect 1 ms 3584 KB Output isn't correct
16 Incorrect 1 ms 3584 KB Output isn't correct
17 Incorrect 2 ms 3584 KB Output isn't correct
18 Incorrect 3 ms 3584 KB Output isn't correct
19 Incorrect 12 ms 3952 KB Output isn't correct
20 Incorrect 11 ms 3952 KB Output isn't correct