Submission #1228502

#	Time	Username	Problem	Language	Result	Execution time	Memory
1228502		Muhammet	Race (IOI11_race)	C++20	Compilation error	0 ms	0 KiB

race

#include "bits/stdc++.h"
#include "race.h"
// #include "grader.cpp"

using namespace std;

#define ll long long

vector <vector <pair <ll, ll>>> v;

vector <ll> dep, depth, s;

int ans, KKK;

vector <map <ll, ll>> mp;

void dfs(int x, int y) {
    s[x] = 1;
    for(auto [i, j] : v[x]) {
        if(i == y) continue;
        dep[i] = dep[x] + j;
        depth[i] = depth[x] + 1;
        dfs(i, x);
        s[x] += s[i];
    }
}

void f(int x, int y) {
    int mx = -1, hv = -1;
    for(auto [i, j] : v[x]) {
        if(i == y) continue;
        f(i, x);
        if(s[i] > mx) {
            hv = i;
            mx = s[i];
        }
    }
    if(~hv) swap(mp[x], mp[hv]);
    for(auto [i, j] : v[x]) {
        if(i == hv or i == y) continue;
        for(auto [k, nm] : mp[i]) {
            if(mp[x].find(k - KKK + dep[x] * 2) == mp[x].end()) continue;
            ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
        }
        for(auto [k, nm] : mp[i]) {
            if(mp[x].find(k) == mp[x].end()) mp[x][k] = nm;
            else mp[x][k] = min(nm, mp[x][k]);
        }
    }
    if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
    mp[x][dep[x]] = depth[x];
}


int best_path(int n, int KK, int h[][2], int l[]) {
    KKK = KK;
    mp.clear();
    v.clear();
    dep.clear();
    depth.clear();
    s.clear();
    v.resize(n+1);
    mp.resize(n+1);
    dep.resize(n+1);
    depth.resize(n+1);
    s.resize(n+1);
    dep[0] = 0;
    depth[0] = 1;
    for(int i = 0; i < n-1; i++) {
        v[h[i][0]].push_back({h[i][1], l[i]});
        v[h[i][1]].push_back({h[i][0], l[i]});
    }
    ans = 1e9;
    dfs(0, -1);
    f(0, -1);
    assert(ans > 0);
    return (ans == 1e9 ? -1 : ans);
}

Compilation message (stderr)

race.cpp: In function 'void f(int, int)':
race.cpp:43:22: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
   43 |             ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:43:22: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   43 |             ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:43:22: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   43 |             ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:43:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |             ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:43:22: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   43 |             ans = min(ans, mp[x][k - KKK + dep[x] * 2] + nm - 2 * depth[x]);
      |                   ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
race.cpp:50:58: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
   50 |     if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
      |                                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:50:58: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   50 |     if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
      |                                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:50:58: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   50 |     if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
      |                                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:50:58: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   50 |     if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
      |                                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~
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:50:58: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   50 |     if(mp[x].find(dep[x] + KKK) != mp[x].end()) ans = min(ans, mp[x][dep[x] + KKK] - depth[x]);
      |                                                       ~~~^~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~~