제출 #1232540

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1232540		nibert	나일강 (IOI24_nile)	C++20	컴파일 에러	0 ms	0 KiB

nile

#include "bits/stdc++.h"
#include "nile.h"
using namespace std;

struct DSU {
    vector<int> parent;
    DSU(int n) : parent(n, -1) {}

    int find(int x) {
        if (parent[x] < 0) return x;
        return parent[x] = find(parent[x]);
    }

    bool same(int x, int y) {
        return find(x) == find(y);
    }

    void unite(int x, int y) {
        x = find(x); y = find(y);
        if (x == y) return;
        if (parent[x] > parent[y]) swap(x, y);
        parent[x] += parent[y];
        parent[y] = x;
    }
};

vector<long long> calculate_costs(vector<int> W, vector<int> A, vector<int> B, vector<int> E) {
    int N = W.size();
    int Q = E.size();

    // 1. Create sorted order of weights (index-based)
    vector<int> ordW(N);
    iota(ordW.begin(), ordW.end(), 0);
    sort(ordW.begin(), ordW.end(), [&](int i, int j) {
        return W[i] < W[j];
    });

    // 2. Create edges between nearby elements in sorted weight order
    vector<array<int, 3>> edges;
    for (int i = 0; i + 1 < N; ++i) {
        int u = ordW[i];
        int v = ordW[i + 1];
        edges.push_back({abs(W[u] - W[v]), u, v});
    }
    for (int i = 0; i + 2 < N; ++i) {
        int u = ordW[i];
        int v = ordW[i + 2];
        edges.push_back({abs(W[u] - W[v]), u, v});
    }
    sort(edges.begin(), edges.end());

    // 3. Offline sort of queries
    vector<int> ordE(Q);
    iota(ordE.begin(), ordE.end(), 0);
    sort(ordE.begin(), ordE.end(), [&](int i, int j) {
        return E[i] < E[j];
    });

    vector<long long> res(Q);
    DSU dsu(N);

    // 4. Start with total cost = all artifacts alone (A[i])
    long long total = accumulate(A.begin(), A.end(), 0LL);

    // 5. Mark each artifact as active and store current cost mode (A[i] used or B[i] used)
    vector<bool> used(N, false);
    int ei = 0;
    for (int qi = 0; qi < Q; ++qi) {
        int d = E[ordE[qi]];
        while (ei < edges.size() && edges[ei][0] <= d) {
            int u = edges[ei][1];
            int v = edges[ei][2];
            int ru = dsu.find(u);
            int rv = dsu.find(v);
            if (ru != rv) {
                // remove solo cost
                total -= A[ru] == -1 ? 0 : A[ru];
                total -= A[rv] == -1 ? 0 : A[rv];

                // unite sets
                dsu.unite(u, v);
                int newRoot = dsu.find(u);

                // compute best upgrade for new set
                long long newCost = 0;
                vector<int> group;
                for (int i = 0; i < N; ++i)
                    if (dsu.find(i) == newRoot)
                        group.push_back(i);

                if (group.size() % 2 == 0) {
                    for (int i : group)
                        newCost += B[i];
                } else {
                    long long extra = LLONG_MAX;
                    for (int i : group)
                        newCost += B[i], extra = min(extra, A[i] - B[i]);
                    newCost += extra;
                }

                // update total
                total += newCost;

                // mark A for root as -1 to prevent double-subtraction
                A[newRoot] = -1;
            }
            ++ei;
        }
        res[ordE[qi]] = total;
    }

    return res;
}

컴파일 시 표준 에러 (stderr) 메시지

nile.cpp: In function 'std::vector<long long int> calculate_costs(std::vector<int>, std::vector<int>, std::vector<int>, std::vector<int>)':
nile.cpp:97:53: error: no matching function for call to 'min(long long int&, __gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
   97 |                         newCost += B[i], extra = min(extra, A[i] - B[i]);
      |                                                  ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:230:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  230 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
nile.cpp:97:53: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
   97 |                         newCost += B[i], extra = min(extra, A[i] - B[i]);
      |                                                  ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/bits/specfun.h:45,
                 from /usr/include/c++/11/cmath:1935,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:41,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_algobase.h:278:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  278 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
nile.cpp:97:53: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'})
   97 |                         newCost += B[i], extra = min(extra, A[i] - B[i]);
      |                                                  ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3449:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3449 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3449:5: note:   template argument deduction/substitution failed:
nile.cpp:97:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   97 |                         newCost += B[i], extra = min(extra, A[i] - B[i]);
      |                                                  ~~~^~~~~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/11/string:52,
                 from /usr/include/c++/11/bits/locale_classes.h:40,
                 from /usr/include/c++/11/bits/ios_base.h:41,
                 from /usr/include/c++/11/ios:42,
                 from /usr/include/c++/11/istream:38,
                 from /usr/include/c++/11/sstream:38,
                 from /usr/include/c++/11/complex:45,
                 from /usr/include/c++/11/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/11/bits/stdc++.h:54,
                 from nile.cpp:1:
/usr/include/c++/11/bits/stl_algo.h:3455:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3455 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/11/bits/stl_algo.h:3455:5: note:   template argument deduction/substitution failed:
nile.cpp:97:53: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   97 |                         newCost += B[i], extra = min(extra, A[i] - B[i]);
      |                                                  ~~~^~~~~~~~~~~~~~~~~~~~