Submission #223058

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
223058	2020-04-14T15:17:04 Z	dolphingarlic	timeismoney (balkan11_timeismoney)	C++14	65 / 100	42 ms	760 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.u == B.u) return A.v < B.v;
    return A.u < B.u;
}

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;
    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	4 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	6 ms	384 KB	Output is correct
6	Correct	5 ms	384 KB	Output is correct
7	Correct	11 ms	512 KB	Output is correct
8	Correct	42 ms	760 KB	Output is correct
9	Correct	4 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	5 ms	384 KB	Output isn't correct
15	Correct	5 ms	384 KB	Output is correct
16	Incorrect	11 ms	512 KB	Output isn't correct
17	Incorrect	12 ms	512 KB	Output isn't correct
18	Incorrect	13 ms	512 KB	Output isn't correct
19	Incorrect	36 ms	640 KB	Output isn't correct
20	Incorrect	37 ms	640 KB	Output isn't correct