제출 #1231141

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1231141		domi	경주 (Race) (IOI11_race)	C++20	컴파일 에러	0 ms	0 KiB

race

#include <bits/stdc++.h>
#include "race.h"

// #define int long long
#define fi first
#define se second

#define sz(a) (int)((a).size())
#define all(a) (a).begin(), (a).end()

#define lsb(x) (x & (-x))
#define vi vector<int>
#define YES { cout << "YES" << endl; return; }
#define NO { cout << "NO" << endl; return; }

using ll = long long;
using pii = std::pair<int64_t, int64_t>;

const int NMAX = 2e5;
const int KMAX = 1e6;

using namespace std;

vector<pii> T[NMAX + 5];
int64_t sz[NMAX + 5], used[NMAX + 5], best[KMAX + 5], n, k, ans;

void prec_sz(int nod, int p = -1) {
    sz[nod] = 1;
    for (auto &[son, cost] : T[nod]) {
        if (son == p || used[son]) continue;
        prec_sz(son, nod);
        sz[nod] += sz[son];
    }
}

int get_centroid(int nod, int p, int total) {
    for (auto &[son, cost] : T[nod]) {
        if (son == p || used[son]) continue;
        if (sz[son] > total / 2)
            return get_centroid(son, nod, total);
    }
    return nod;
}

void update(int nod, int p, int sum, int depth) {
    if (sum > k) return;
    best[sum] = min(best[sum], depth);
    for (auto &[son, cost] : T[nod]) {
        if (son == p || used[son]) continue;
        update(son, nod, sum + cost, depth + 1);
    }
}

void remove(int nod, int p, int sum, int depth) {
    if (sum > k) return;
    best[sum] = LLONG_MAX;
    for (auto &[son, cost] : T[nod]) {
        if (son == p || used[son]) continue;
        remove(son, nod, sum + cost, depth + 1);
    }
}

void query(int nod, int p, int sum, int depth) {
    if (sum > k) return;
    if (best[k - sum] != LLONG_MAX)
        ans = min(ans, best[k - sum] + depth);
    for (auto &[son, cost] : T[nod]) {
        if (son == p || used[son]) continue;
        query(son, nod, sum + cost, depth + 1);
    }
}

void solve(int nod) {
    prec_sz(nod);
    int centroid = get_centroid(nod, -1, sz[nod]);
    used[centroid] = true;

    best[0] = 0;

    for (auto &[son, cost] : T[centroid]) {
        if (used[son]) continue;
        query(son, centroid, cost, 1);
        update(son, centroid, cost, 1);
    }

    for (auto &[son, cost] : T[centroid]) {
        if (used[son]) continue;
        remove(son, centroid, cost, 1);
    }

    for (auto &[son, cost] : T[centroid]) {
        if (!used[son])
            solve(son);
    }
}

int best_path(int N, int K, int H[][2], int L[]) {
    n = N, k = K;
    ans = LLONG_MAX;

    for (int i = 0; i < n; i++) {
        T[i].clear();
        used[i] = 0;
    }

    for (int i = 0; i <= k; i++) best[i] = LLONG_MAX;

    for (int i = 0; i < n - 1; i++) {
        int u = H[i][0], v = H[i][1], w = L[i];
        T[u].emplace_back(v, w);
        T[v].emplace_back(u, w);
    }

    solve(0);
    return (ans == LLONG_MAX ? -1 : ans);
}

// signed main() {
//     cin.tie(nullptr)->sync_with_stdio(false);
//
//     int N, K;
//     cin >> N >> K;
//
//     int H[NMAX][2];
//     int L[NMAX];
//
//     for (int i = 0; i < N - 1; i++) {
//         cin >> H[i][0] >> H[i][1] >> L[i];
//     }
//
//     int answer = best_path(N, K, H, L);
//     cout << answer << '\n';
//
//     return 0;
// }

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

race.cpp: In function 'void update(int, int, int, int)':
race.cpp:47:20: error: no matching function for call to 'min(int64_t&, int&)'
   47 |     best[sum] = min(best[sum], depth);
      |                 ~~~^~~~~~~~~~~~~~~~~~
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 race.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:
race.cpp:47:20: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   47 |     best[sum] = min(best[sum], depth);
      |                 ~~~^~~~~~~~~~~~~~~~~~
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 race.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:
race.cpp:47:20: note:   deduced conflicting types for parameter 'const _Tp' ('long int' and 'int')
   47 |     best[sum] = min(best[sum], depth);
      |                 ~~~^~~~~~~~~~~~~~~~~~
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 race.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:
race.cpp:47:20: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   47 |     best[sum] = min(best[sum], depth);
      |                 ~~~^~~~~~~~~~~~~~~~~~
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 race.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:
race.cpp:47:20: note:   mismatched types 'std::initializer_list<_Tp>' and 'long int'
   47 |     best[sum] = min(best[sum], depth);
      |                 ~~~^~~~~~~~~~~~~~~~~~