Submission #1011145

#	Time	Username	Problem	Language	Result	Execution time	Memory
1011145		avi_sri	Training (IOI07_training)	C++17	0 / 100	3 ms	604 KiB

training

#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
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 7
• Subtask 5: 0 / 9
• Subtask 6: 0 / 9
• Subtask 7: 0 / 9
• Subtask 8: 0 / 9
• Subtask 9: 0 / 9
• Subtask 10: 0 / 9
• Subtask 11: 0 / 9