Submission #292465

#	Time	Username	Problem	Language	Result	Execution time	Memory
292465		davooddkareshki	Race (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

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

using namespace std;

typedef long long ll;
typedef long double ld;

//#define int long long
#define F first
#define S second
#define pii pair<int,int>
#define mpr make_pair

const int maxn = 2e5+10;
const ll inf = 1e18+10;
const int mod = 1e9+7;
const int N = 2e7+10;

int K;
map<int,int> *mp[maxn];
int st[maxn], h[maxn], sum[maxn];
vector<pii> g[maxn];

void pfs(int v, int p = -1)
{
   st[v] = 1;
   for(auto e : g[v])
   {
      int u = e.F, w = e.S;
      if(u != p)
      {
         sum[u] = sum[v] + w;
         h[u] = h[v] + 1;

         pfs(u,v);
         st[v] += st[u];
      }
   }
}

ll ans = inf;
void dfs(int v, int p = -1)
{
   int big = -1;
   for(auto e : g[v])
   {
      int u = e.F;
      if(u != p)
      {
         dfs(u,v);
         if(big == -1) big = u;
         else if(st[u] > st[big]) big = u;
      }
   }

   if(big != -1) mp[v] = mp[big];
   else mp[v] = new map<int,int>;
   (*mp[v])[sum[v]] = h[v];

   if((*mp[v]).count(K+sum[v]))
      ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);

   for(auto e : g[v])
   {
      int u = e.F, w = e.S;
      if(u != p && u != big)
      {
         for(auto X : (*mp[u]))
         {
            int sm = X.F, Mn = X.S;
            if((*mp[v]).count(K-sm+2*sum[v]))
            {
               int road = Mn + (*mp[v])[K-sm] - 2 * h[v];
               ans = min(ans,road);
            }
         }

         for(auto X : (*mp[u]))
         {
            int sm = X.F, Mn = X.S;
            if(!(*mp[v]).count(sm)) (*mp[v])[sm] = Mn;
            else (*mp[v])[sm] = min((*mp[v])[sm], Mn);
         }
      }
   }
}

int best_path(int n, int k, int h[][2], int l[])
{
   //cin>> n >> K;
   K = k;
   for(int i = 0, u, v, w; i < n-1; i++)
   {
      //cin>> u >> v >> w;
      u = h[i][0], v = h[i][1], w = l[i];
      u++; v++;
      g[u].push_back({v,w});
      g[v].push_back({u,w});
   }

   pfs(1); dfs(1);
   if(ans == inf) return -1;
   else return ans;
}

Compilation message (stderr)

race.cpp: In function 'void dfs(int, int)':
race.cpp:62:47: error: no matching function for call to 'min(ll&, std::map<int, int>::mapped_type)'
   62 |       ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
      |                                               ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  198 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note:   template argument deduction/substitution failed:
race.cpp:62:47: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type' {aka 'int'})
   62 |       ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
      |                                               ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  246 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note:   template argument deduction/substitution failed:
race.cpp:62:47: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'std::map<int, int>::mapped_type' {aka 'int'})
   62 |       ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
      |                                               ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3444 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
race.cpp:62:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   62 |       ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
      |                                               ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3450 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:62:47: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   62 |       ans = min(ans, (*mp[v])[K+sum[v]] - h[v]);
      |                                               ^
race.cpp:75:34: error: no matching function for call to 'min(ll&, int&)'
   75 |                ans = min(ans,road);
      |                                  ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:198:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)'
  198 |     min(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:198:5: note:   template argument deduction/substitution failed:
race.cpp:75:34: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   75 |                ans = min(ans,road);
      |                                  ^
In file included from /usr/include/c++/9/bits/specfun.h:45,
                 from /usr/include/c++/9/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:246:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)'
  246 |     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:246:5: note:   template argument deduction/substitution failed:
race.cpp:75:34: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   75 |                ans = min(ans,road);
      |                                  ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3444:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3444 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3444:5: note:   template argument deduction/substitution failed:
race.cpp:75:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   75 |                ans = min(ans,road);
      |                                  ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3450:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3450 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:75:34: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   75 |                ans = min(ans,road);
      |                                  ^
race.cpp:66:20: warning: unused variable 'w' [-Wunused-variable]
   66 |       int u = e.F, w = e.S;
      |                    ^