oj.uz

Submission #222991

# Submission time Handle Problem Language Result Execution time Memory
222991 2020-04-14T12:51:56 Z dolphingarlic timeismoney (balkan11_timeismoney) C++14
50 / 100
 12 ms 512 KB 
#include <bits/stdc++.h>
#define FOR(i, x, y) for (int i = x; i < y; i++)
typedef long long ll;
using namespace std;

struct Line {
    int u, v, t, c;

    bool operator<(Line B) { return t + c + t * c < B.t + B.c + t * c; }
} lines[10000];

int cmp[200];

int find(int A) {
    while (A != cmp[A]) cmp[A] = cmp[cmp[A]], A = cmp[A];
    return A;
}

void onion(int A, int B) { cmp[find(A)] = cmp[find(B)]; }

int main() {
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    int n, m;
    cin >> n >> m;
    FOR(i, 0, m) cin >> lines[i].u >> lines[i].v >> lines[i].t >> lines[i].c;
    sort(lines, lines + m);
    iota(cmp, cmp + n, 0);

    vector<Line> res;
    int t = 0, c = 0;
    FOR(i, 0, m) {
        if (find(lines[i].u) != find(lines[i].v)) {
            t += lines[i].t, c += lines[i].c;
            onion(lines[i].u, lines[i].v);
            res.push_back(lines[i]);
        }
    }

    cout << t << ' ' << c << '\n';
    for (Line i : res) cout << i.u << ' ' << i.v << '\n';
    return 0;
}

Subtask #1
50.0 / 100.0

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