oj.uz

Submission #1011145

# Submission time Handle Problem Language Result Execution time Memory
1011145 2024-06-29T23:16:55 Z avi_sri Training (IOI07_training) C++17
0 / 100
 3 ms 604 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <climits>

using namespace std;

struct Edge {
    int u, v, cost;
    bool paved;
};

vector<Edge> edges;
vector<int> parent, rank_arr;
vector<int> even_cycle_costs;

int find(int u) {
    if (parent[u] != u)
        parent[u] = find(parent[u]);
    return parent[u];
}

void unite(int u, int v) {
    int root_u = find(u);
    int root_v = find(v);
    if (root_u != root_v) {
        if (rank_arr[root_u] > rank_arr[root_v]) {
            parent[root_v] = root_u;
        } else if (rank_arr[root_u] < rank_arr[root_v]) {
            parent[root_u] = root_v;
        } else {
            parent[root_v] = root_u;
            rank_arr[root_u]++;
        }
    }
}

bool has_even_cycle(int n) {
    parent.resize(n + 1);
    rank_arr.resize(n + 1, 0);
    for (int i = 1; i <= n; ++i) {
        parent[i] = i;
    }

    for (const auto& edge : edges) {
        if (edge.paved) {
            if (find(edge.u) == find(edge.v)) {
                return true;
            } else {
                unite(edge.u, edge.v);
            }
        }
    }
    return false;
}

int main() {
    int N, M;
    cin >> N >> M;

    for (int i = 0; i < M; ++i) {
        int A, B, C;
        cin >> A >> B >> C;
        edges.push_back({A, B, C, C == 0});
    }

    // Check for even cycles in the paved road tree
    if (has_even_cycle(N)) {
        cout << 0 << endl;
        return 0;
    }

    // Gather all costs of unpaved roads
    for (const auto& edge : edges) {
        if (!edge.paved) {
            even_cycle_costs.push_back(edge.cost);
        }
    }

    // Sort the costs to find the minimum cost to block the roads
    sort(even_cycle_costs.begin(), even_cycle_costs.end());

    int total_cost = 0;
    for (int cost : even_cycle_costs) {
        total_cost += cost;
    }

    cout << total_cost << endl;
    return 0;
}

Subtask #1
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #2
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 10.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 7.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #6
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 0 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #7
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 344 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #8
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #9
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 2 ms 600 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #10
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 1 ms 348 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #11
0 / 9.0

# Verdict Execution time Memory Grader output
1 Incorrect 3 ms 604 KB Output isn't correct
2 Halted 0 ms 0 KB -