답안 #1057646

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1057646	2024-08-14T02:23:40 Z	vjudge1	Sirni (COCI17_sirni)	C++17	컴파일 오류	0 ms	0 KB

sirni

#include <bits/stdc++.h>
using namespace std;

using ll = long long;

const int MAXN = 1e5 + 5;
int parent[MAXN], size[MAXN];

// Union-Find with path compression and union by size
int find(int u) {
    if (u != parent[u])
        parent[u] = find(parent[u]);
    return parent[u];
}

void unionSets(int u, int v) {
    u = find(u);
    v = find(v);
    if (u != v) {
        if (size[u] < size[v])
            swap(u, v);
        parent[v] = u;
        size[u] += size[v];
    }
}

int main() {
    int n;
    cin >> n;
    vector<int> P(n);
    for (int i = 0; i < n; ++i) {
        cin >> P[i];
        parent[i] = i;
        size[i] = 1;
    }

    ll mst_weight = 0;
    int components = n;

    while (components > 1) {
        vector<pair<int, pair<int, int>>> min_edge(n, {INT_MAX, {-1, -1}});

        // Find the minimum outgoing edge for each component
        for (int u = 0; u < n; ++u) {
            for (int v = 0; v < n; ++v) {
                if (u != v) {
                    int root_u = find(u);
                    int root_v = find(v);
                    if (root_u != root_v) {
                        int weight = min(P[u] % P[v], P[v] % P[u]);
                        if (weight < min_edge[root_u].first) {
                            min_edge[root_u] = {weight, {u, v}};
                        }
                    }
                }
            }
        }

        // Add the minimum edges to the MST
        for (int u = 0; u < n; ++u) {
            auto [weight, edge] = min_edge[u];
            int v = edge.second;
            if (weight != INT_MAX && find(u) != find(v)) {
                mst_weight += weight;
                unionSets(u, v);
                components--;
            }
        }
    }

    cout << mst_weight << "\n";
    return 0;
}

Compilation message

sirni.cpp: In function 'void unionSets(int, int)':
sirni.cpp:20:13: error: reference to 'size' is ambiguous
   20 |         if (size[u] < size[v])
      |             ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
sirni.cpp:7:19: note:                 'int size [100005]'
    7 | int parent[MAXN], size[MAXN];
      |                   ^~~~
sirni.cpp:20:23: error: reference to 'size' is ambiguous
   20 |         if (size[u] < size[v])
      |                       ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
sirni.cpp:7:19: note:                 'int size [100005]'
    7 | int parent[MAXN], size[MAXN];
      |                   ^~~~
sirni.cpp:23:9: error: reference to 'size' is ambiguous
   23 |         size[u] += size[v];
      |         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
sirni.cpp:7:19: note:                 'int size [100005]'
    7 | int parent[MAXN], size[MAXN];
      |                   ^~~~
sirni.cpp:23:20: error: reference to 'size' is ambiguous
   23 |         size[u] += size[v];
      |                    ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
sirni.cpp:7:19: note:                 'int size [100005]'
    7 | int parent[MAXN], size[MAXN];
      |                   ^~~~
sirni.cpp: In function 'int main()':
sirni.cpp:34:9: error: reference to 'size' is ambiguous
   34 |         size[i] = 1;
      |         ^~~~
In file included from /usr/include/c++/10/string:54,
                 from /usr/include/c++/10/bits/locale_classes.h:40,
                 from /usr/include/c++/10/bits/ios_base.h:41,
                 from /usr/include/c++/10/ios:42,
                 from /usr/include/c++/10/istream:38,
                 from /usr/include/c++/10/sstream:38,
                 from /usr/include/c++/10/complex:45,
                 from /usr/include/c++/10/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:54,
                 from sirni.cpp:1:
/usr/include/c++/10/bits/range_access.h:254:5: note: candidates are: 'template<class _Tp, long unsigned int _Nm> constexpr std::size_t std::size(const _Tp (&)[_Nm])'
  254 |     size(const _Tp (&)[_Nm]) noexcept
      |     ^~~~
/usr/include/c++/10/bits/range_access.h:245:5: note:                 'template<class _Container> constexpr decltype (__cont.size()) std::size(const _Container&)'
  245 |     size(const _Container& __cont) noexcept(noexcept(__cont.size()))
      |     ^~~~
sirni.cpp:7:19: note:                 'int size [100005]'
    7 | int parent[MAXN], size[MAXN];
      |                   ^~~~