oj.uz

Submission #223078

# Submission time Handle Problem Language Result Execution time Memory
223078 2020-04-14T16:17:43 Z dolphingarlic timeismoney (balkan11_timeismoney) C++14
5 / 100
 9 ms 1280 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;
    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 + t + c;
            Line to_remove;
            for (Line j : in_cycle) {
                if ((t - j.t + lines[i].t) * (c - j.c + lines[i].c) + 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) + 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
5.0 / 100.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 384 KB Output is correct
2 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
3 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
4 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
5 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
6 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
7 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
8 Runtime error 9 ms 1280 KB Execution killed with signal 11 (could be triggered by violating memory limits)
9 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
10 Runtime error 5 ms 384 KB Execution killed with signal 11 (could be triggered by violating memory limits)
11 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
12 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
13 Runtime error 5 ms 512 KB Execution killed with signal 11 (could be triggered by violating memory limits)
14 Runtime error 5 ms 640 KB Execution killed with signal 11 (could be triggered by violating memory limits)
15 Runtime error 5 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
16 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
17 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
18 Runtime error 6 ms 768 KB Execution killed with signal 11 (could be triggered by violating memory limits)
19 Runtime error 8 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)
20 Runtime error 9 ms 1024 KB Execution killed with signal 11 (could be triggered by violating memory limits)