제출 #417951

#제출 시각아이디문제언어결과실행 시간메모리
417951temurbek_khujaev경주 (Race) (IOI11_race)C++17
컴파일 에러
0 ms0 KiB
#include "race.h"
#include <bits/stdc++.h>

#define N 200200
using namespace std;

vector<pair<int, int> > g[N];
int d[N];
int p[N];

int get_centroid(int v, int parent, int n, int &centroid) {
    int size = 1;
    for (auto[x, y]:g[v]) {
        if (x != parent && d[x] == -1) {
            size += get_centroid(x, v, n, centroid);
        }
    }
    if (size * 2 >= n && centroid == -1) centroid = v;
    return size;
}

int K;
int ans = 1e9;

void get_compo_dists(int v, int dist, int len, int pass_limit, vector<pair<int, int> > &vec, int p = -1) {
    if (dist > K) return;
    vec.emplace_back(dist, len);
    for (auto[x, y]:g[v]) {
        if ((d[x] > pass_limit || d[x] == -1) && p != x) {
            get_compo_dists(x, dist + y, len + 1, pass_limit, vec, v);
        }
    }
}

void build(int v, int parent, int depth, int n) {
    int centroid = -1;
    get_centroid(v, -1, n, centroid);
    if (centroid == -1) centroid = v;
    d[centroid] = depth;
    p[centroid] = parent;
    map<int, int> dist = {0, 0};

    for (auto[x, y]:g[centroid]) {
        if (d[x] == -1) {
            build(x, centroid, depth + 1, (n + 1) / 2);
            vector<pair<int, int>> vec;
            get_compo_dists(centroid, 0, 0, d[centroid], vec);
            for (auto[distance, cost]: vec) {
                if (dist.count(K - distance)) {
                    ans = min(ans, cost + dist[distance]);
                }
            }

            for (auto[distance, cost]: vec) {
                if (dist.count(distance) == 0) {
                    dist[distance] = cost;
                } else dist[distance] = min(dist[distance], cost);
            }
        }


    }
//    cerr << "Centroid = " << centroid << endl;
//    for (auto[x, y]:dist) {
//        cerr << x << ' ' << y << endl;
//    }
}

int best_path(int n, int K, int H[][2], int L[]) {
    ::K = K;
    for (int i = 0; i < n - 1; i++) {
        g[H[i][0]].emplace_back(H[i][1], L[i]);
        g[H[i][1]].emplace_back(H[i][0], L[i]);
    }
    fill(d, d + N, -1);
    build(0, -1, 1, n);

    return (ans == 1e9 ? -1 : ans);
}

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

In file included from /usr/include/c++/10/map:61,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_map.h: In instantiation of 'std::map<_Key, _Tp, _Compare, _Alloc>::map(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]':
race.cpp:41:31:   required from here
/usr/include/c++/10/bits/stl_map.h:275:31: error: no matching function for call to 'std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique(int&, int&)'
  275 |  { _M_t._M_insert_range_unique(__first, __last); }
      |    ~~~~~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~~~~
In file included from /usr/include/c++/10/map:60,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:81,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_tree.h:1105:2: note: candidate: 'template<class _InputIterator> std::__enable_if_t<std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Val = std::pair<const int, int>; _KeyOfValue = std::_Select1st<std::pair<const int, int> >; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
 1105 |  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1105:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<std::is_same<std::pair<const int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value, void> std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique<_InputIterator>(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/10/bits/stl_map.h:275:31:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::map(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
race.cpp:41:31:   required from here
/usr/include/c++/10/bits/stl_tree.h:1105:2: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
/usr/include/c++/10/bits/stl_map.h: In instantiation of 'std::map<_Key, _Tp, _Compare, _Alloc>::map(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]':
race.cpp:41:31:   required from here
/usr/include/c++/10/bits/stl_tree.h:1114:2: note: candidate: 'template<class _InputIterator> std::__enable_if_t<(! std::is_same<_Val, typename std::iterator_traits<_InputIterator>::value_type>::value)> std::_Rb_tree<_Key, _Val, _KeyOfValue, _Compare, _Alloc>::_M_insert_range_unique(_InputIterator, _InputIterator) [with _InputIterator = _InputIterator; _Key = int; _Val = std::pair<const int, int>; _KeyOfValue = std::_Select1st<std::pair<const int, int> >; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
 1114 |  _M_insert_range_unique(_InputIterator __first, _InputIterator __last)
      |  ^~~~~~~~~~~~~~~~~~~~~~
/usr/include/c++/10/bits/stl_tree.h:1114:2: note:   template argument deduction/substitution failed:
/usr/include/c++/10/bits/stl_tree.h: In substitution of 'template<class _InputIterator> std::__enable_if_t<(! std::is_same<std::pair<const int, int>, typename std::iterator_traits< <template-parameter-1-1> >::value_type>::value), void> std::_Rb_tree<int, std::pair<const int, int>, std::_Select1st<std::pair<const int, int> >, std::less<int>, std::allocator<std::pair<const int, int> > >::_M_insert_range_unique<_InputIterator>(_InputIterator, _InputIterator) [with _InputIterator = int]':
/usr/include/c++/10/bits/stl_map.h:275:31:   required from 'std::map<_Key, _Tp, _Compare, _Alloc>::map(_InputIterator, _InputIterator) [with _InputIterator = int; _Key = int; _Tp = int; _Compare = std::less<int>; _Alloc = std::allocator<std::pair<const int, int> >]'
race.cpp:41:31:   required from here
/usr/include/c++/10/bits/stl_tree.h:1113:52: error: no type named 'value_type' in 'struct std::iterator_traits<int>'
 1113 |  __enable_if_t<!__same_value_type<_InputIterator>::value>
      |                                                    ^~~~~