Submission #1011144

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1011144	2024-06-29T23:15:34 Z	avi_sri	Training (IOI07_training)	C++14	Compilation error	0 ms	0 KB

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;
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[root_u] > rank[root_v]) {
            parent[root_v] = root_u;
        } else if (rank[root_u] < rank[root_v]) {
            parent[root_u] = root_v;
        } else {
            parent[root_v] = root_u;
            rank[root_u]++;
        }
    }
}

bool has_even_cycle(int n) {
    parent.resize(n + 1);
    rank.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;
}

Compilation message

training.cpp: In function 'void unite(int, int)':
training.cpp:27:13: error: reference to 'rank' is ambiguous
   27 |         if (rank[root_u] > rank[root_v]) {
      |             ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~
training.cpp:27:28: error: reference to 'rank' is ambiguous
   27 |         if (rank[root_u] > rank[root_v]) {
      |                            ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~
training.cpp:29:20: error: reference to 'rank' is ambiguous
   29 |         } else if (rank[root_u] < rank[root_v]) {
      |                    ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~
training.cpp:29:35: error: reference to 'rank' is ambiguous
   29 |         } else if (rank[root_u] < rank[root_v]) {
      |                                   ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~
training.cpp:33:13: error: reference to 'rank' is ambiguous
   33 |             rank[root_u]++;
      |             ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~
training.cpp: In function 'bool has_even_cycle(int)':
training.cpp:40:5: error: reference to 'rank' is ambiguous
   40 |     rank.resize(n + 1, 0);
      |     ^~~~
In file included from /usr/include/c++/10/bits/move.h:57,
                 from /usr/include/c++/10/bits/nested_exception.h:40,
                 from /usr/include/c++/10/exception:148,
                 from /usr/include/c++/10/ios:39,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from training.cpp:1:
/usr/include/c++/10/type_traits:1359:12: note: candidates are: 'template<class> struct std::rank'
 1359 |     struct rank
      |            ^~~~
training.cpp:14:21: note:                 'std::vector<int> rank'
   14 | vector<int> parent, rank;
      |                     ^~~~