Submission #711908

#	Time	Username	Problem	Language	Result	Execution time	Memory
711908		Hoff22	경주 (Race) (IOI11_race)	C++17	Compilation error	0 ms	0 KiB

race

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

#define N 200000
#define MAX 1000000000
#define E 0.00000001
#define MOD 1000000007
#define INF 0x3f3f3f3f
#define INFll 0x3f3f3f3f3f3f3f3fll
#define LEFT(x) (2 * x)
#define RIGHT(x) (2 * x + 1)
#define se second
#define fi first

using namespace std;

typedef long long ll;

vector<ll> g[N+1];
map<pair<ll,ll>, ll> e;
map<ll,ll> d[N+1];
ll dist[N+1];
ll sz[N+1];
int ans = -1;

void prec(ll u, ll p){
	dist[u] = dist[p] + e[{u,p}];
	for(ll v : g[u]){
		if(v == p) continue;
		prec(v, u);
	}
}

void solve(ll u, ll p, ll depth, ll k){
	
	ll big = -1;
	sz[u] = 1;
	
	for(ll v : g[u]){
		if(v == p) continue;
		solve(v, u, depth+1, k);
		sz[u] += sz[v];
		if(big == -1 or sz[v] > sz[big]) big = v;
	}

	if(big == -1){
		d[u][dist[u]] = depth;	
		return;
	}

	swap(d[u], d[big]);

	d[u][dist[u]] = depth;

	if(d[u].count(k + dist[u])){
		if(ans == -1) ans = d[u][k + dist[u]] - depth;
		else  ans = min(ans, d[u][k + dist[u]] - depth);
	}

	for(ll v : g[u]){
		if(v == p or v == big) continue; 
		for(auto i : d[v]){
			if(d[u].count(i.fi)){
				d[u][i.fi] = min(d[u][i.fi], i.se);
			}
			else{
				d[u][i.fi] = i.se;
			}

			ll want = k + 2 * dist[u] - i.fi;
			if(d[u].count(want)){
				if(ans == -1) ans = (d[u][i.fi] - depth) + (d[u][want] - depth); 
				else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
			}
		}
	}
}

int best_path(int n, int k, int (*h)[2], int* l){
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);

	for(ll i = 0; i <= n; i++){
		g[i].clear();
		dist[i] = 0;
		sz[i] = 0;
		d[i].clear();
	}
	ans = -1;
	e.clear();

	for(ll i = 0; i < n-1; i++){
		ll u, v, w;
		u = h[i][0];
		v = h[i][1];
		w = l[i];

		u++;
		v++;

		g[u].push_back(v);
		g[v].push_back(u);
		e[{u,v}] = w;
		e[{v,u}] = w;
	}

	prec(1,0);
	solve(1, 0, 0, k);

	return ans;
}

Compilation message (stderr)

race.cpp: In function 'void solve(ll, ll, ll, ll)':
race.cpp:57:49: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
   57 |   else  ans = min(ans, d[u][k + dist[u]] - depth);
      |                                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
race.cpp:57:49: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   57 |   else  ans = min(ans, d[u][k + dist[u]] - depth);
      |                                                 ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
race.cpp:57:49: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   57 |   else  ans = min(ans, d[u][k + dist[u]] - depth);
      |                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
race.cpp:57:49: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   57 |   else  ans = min(ans, d[u][k + dist[u]] - depth);
      |                                                 ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
race.cpp:57:49: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   57 |   else  ans = min(ans, d[u][k + dist[u]] - depth);
      |                                                 ^
race.cpp:73:68: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
   73 |     else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
      |                                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:230:5: note:   template argument deduction/substitution failed:
race.cpp:73:68: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   73 |     else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
      |                                                                    ^
In file included from /usr/include/c++/10/bits/specfun.h:45,
                 from /usr/include/c++/10/cmath:1927,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:41,
                 from race.cpp:2:
/usr/include/c++/10/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++/10/bits/stl_algobase.h:278:5: note:   template argument deduction/substitution failed:
race.cpp:73:68: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type' {aka 'long long int'})
   73 |     else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
      |                                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3468:5: note: candidate: 'template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)'
 3468 |     min(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3468:5: note:   template argument deduction/substitution failed:
race.cpp:73:68: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   73 |     else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
      |                                                                    ^
In file included from /usr/include/c++/10/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:65,
                 from race.cpp:2:
/usr/include/c++/10/bits/stl_algo.h:3474:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)'
 3474 |     min(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/10/bits/stl_algo.h:3474:5: note:   template argument deduction/substitution failed:
race.cpp:73:68: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   73 |     else ans = min(ans, (d[u][i.fi] - depth) + (d[u][want] - depth));
      |                                                                    ^