Submission #223056

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223056	2020-04-14T15:12:37 Z	dolphingarlic	timeismoney (balkan11_timeismoney)	C++14	65 / 100	56 ms	640 KB

timeismoney

#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;
    ll t, c;
} lines[10000];

bool operator<(Line A, Line B) {
    if (A.t + A.c == B.t + B.c) {
        if (A.u == B.u) return A.v < B.v;
        return A.u < B.u;
    }
    return A.t + A.c > B.t + B.c;
}

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)]; }

set<Line> graph[200];
bool has_cycle[200];
vector<Line> in_cycle;

void dfs(int target, int node, int parent = -1) {
    if (node == target) {
        has_cycle[node] = true;
        return;
    }
    for (Line i : graph[node]) {
        if (i.u != parent && i.v != parent) {
            dfs(target, node == i.u ? i.v : i.u, node);
            if (has_cycle[node == i.u ? i.v : i.u]) {
                in_cycle.push_back(i);
                has_cycle[node] = true;
                return;
            }
        }
    }
}

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);

    set<Line> res;
    ll 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.insert(lines[i]);
            graph[lines[i].u].insert(lines[i]);
            graph[lines[i].v].insert(lines[i]);
        } else {
            fill(has_cycle, has_cycle + n, false);
            in_cycle.clear();
            dfs(lines[i].u, lines[i].v);

            ll best = t * c;
            Line to_remove;
            for (Line j : in_cycle) {
                if ((t - j.t + lines[i].t) * (c - j.c + lines[i].c) < best) {
                    best = (t - j.t + lines[i].t) * (c - j.c + lines[i].c);
                    to_remove = j;
                }
            }
            if (best != t * c) {
                res.insert(lines[i]);
                assert(res.find(to_remove) != res.end());
                res.erase(to_remove);
                graph[to_remove.u].erase(to_remove);
                graph[to_remove.v].erase(to_remove);
                graph[lines[i].u].insert(lines[i]);
                graph[lines[i].v].insert(lines[i]);
                t += lines[i].t - to_remove.t;
                c += lines[i].c - to_remove.c;
            }
        }
    }

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

Subtask #1

65.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	15 ms	384 KB	Output is correct
8	Correct	56 ms	640 KB	Output is correct
9	Correct	5 ms	384 KB	Output is correct
10	Correct	5 ms	384 KB	Output is correct
11	Incorrect	5 ms	384 KB	Output isn't correct
12	Correct	5 ms	384 KB	Output is correct
13	Correct	5 ms	384 KB	Output is correct
14	Incorrect	6 ms	384 KB	Output isn't correct
15	Correct	5 ms	384 KB	Output is correct
16	Incorrect	13 ms	384 KB	Output isn't correct
17	Incorrect	13 ms	384 KB	Output isn't correct
18	Incorrect	13 ms	384 KB	Output isn't correct
19	Incorrect	43 ms	640 KB	Output isn't correct
20	Incorrect	48 ms	640 KB	Output isn't correct