Submission #212470

#	Time	Username	Problem	Language	Result	Execution time	Memory
212470		_qVp_	Race (IOI11_race)	C++14	Compilation error	0 ms	0 KiB

race

#include <bits/stdc++.h>

using namespace std;

const int MAXN = 2e5 + 10;
const int oo = 1e9;

typedef pair < int, int > II;

#define z id[j]

int sz[MAXN], depth[MAXN];
long long sum[MAXN];
vector < II > adj[MAXN];
vector < int > vec[MAXN];
map < long long, long long > path;
int h[MAXN][2], l[MAXN], big[MAXN];
int n, k;
int ans = oo, cnt = 0;
int in[MAXN], out[MAXN], id[MAXN];

void dfs(int u, int p) {
	sz[u] = 1;
	in[u] = ++cnt;
	id[cnt] = u;
	for(auto cur : adj[u]) {
		int v = cur.first, w = cur.second;
		if (v == p)
			continue;
		depth[v] = depth[u] + 1;
		sum[v] = sum[u] + w;
		dfs(v, u);
		sz[u] += sz[v];
	}
	out[u] = cnt;
}

void modify(int u, int k) {
	long long sumNow = sum[u]; 
	if (k == -1) {
		path[sumNow] = 0;
	} else {
		int tmp = path[sumNow];
		if (tmp == 0)
			tmp = oo;
		path[sumNow] = min(tmp, depth[u]);
	}
}

void sack(int u, int p, int keep) {
	int szMax = -1, bigChild = -1;
	
	for(auto cur : adj[u]) {
		int v = cur.first;
		if (v == p)
			continue;
		if (sz[v] > szMax) {
			sz[v] = szMax;
			bigChild = v;
		}
	}
	
	for(auto cur : adj[u]) {
		int v = cur.first;
		if (v != bigChild && v != p)
			sack(v, u, 0);
	}
	
	if (bigChild != -1) {
		sack(bigChild, u, 1);
		big[bigChild] = 1;
	}
	
	for(auto cur : adj[u]) {
		int v = cur.first;
		if (v == p || v == bigChild)
			continue;
		for(int j = in[v]; j <= out[v]; j++) {
			long long need = k + sum[u] * 2 - sum[z];
			if (path[need]) 
				ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
		}
		for(int j = in[v]; j <= out[v]; j++) {
			modify(z, 1);
		}
	}
	
	modify(u, 1);
	if (path[k + sum[u]])
			ans = min(ans, path[k + sum[u]] - depth[u]);
	if (bigChild != -1)
		big[bigChild] = 0;
	if (!keep) {
		for(int j = in[u]; j <= out[u]; j++) {
			modify(z, -1);
		}
	}
	
}

int solve() {
	dfs(0, -1);
	sack(0, -1, 1);
	return (ans == oo ? -1 : ans);
}

int best_path(int N, int K, int H[][2], int L[]) {
	n = N, k = K;
	for(int i = 0; i < n - 1; i++) {
		int u = H[i][0], v = H[i][1], w = L[i];
		adj[u].push_back(II(v, w));
		adj[v].push_back(II(u, w));
	}
	return solve();
}

Compilation message (stderr)

race.cpp: In function 'void sack(int, int, int)':
race.cpp:81:56: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
     ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
                                                        ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
race.cpp:81:56: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type {aka long long int}')
     ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
                                                        ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
race.cpp:81:56: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type {aka long long int}')
     ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
                                                        ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:81:56: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
                                                        ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
race.cpp:81:56: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
     ans = min(ans, path[need] + depth[z] - 2 * depth[u]);
                                                        ^
race.cpp:90:46: error: no matching function for call to 'min(int&, std::map<long long int, long long int>::mapped_type)'
    ans = min(ans, path[k + sum[u]] - depth[u]);
                                              ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:195:5: note: candidate: template<class _Tp> constexpr const _Tp& std::min(const _Tp&, const _Tp&)
     min(const _Tp& __a, const _Tp& __b)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:195:5: note:   template argument deduction/substitution failed:
race.cpp:90:46: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type {aka long long int}')
    ans = min(ans, path[k + sum[u]] - depth[u]);
                                              ^
In file included from /usr/include/c++/7/bits/char_traits.h:39:0,
                 from /usr/include/c++/7/ios:40,
                 from /usr/include/c++/7/istream:38,
                 from /usr/include/c++/7/sstream:38,
                 from /usr/include/c++/7/complex:45,
                 from /usr/include/c++/7/ccomplex:39,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:52,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algobase.h:243:5: note: candidate: template<class _Tp, class _Compare> constexpr const _Tp& std::min(const _Tp&, const _Tp&, _Compare)
     min(const _Tp& __a, const _Tp& __b, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algobase.h:243:5: note:   template argument deduction/substitution failed:
race.cpp:90:46: note:   deduced conflicting types for parameter 'const _Tp' ('int' and 'std::map<long long int, long long int>::mapped_type {aka long long int}')
    ans = min(ans, path[k + sum[u]] - depth[u]);
                                              ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3450:5: note: candidate: template<class _Tp> constexpr _Tp std::min(std::initializer_list<_Tp>)
     min(initializer_list<_Tp> __l)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3450:5: note:   template argument deduction/substitution failed:
race.cpp:90:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
    ans = min(ans, path[k + sum[u]] - depth[u]);
                                              ^
In file included from /usr/include/c++/7/algorithm:62:0,
                 from /usr/include/x86_64-linux-gnu/c++/7/bits/stdc++.h:65,
                 from race.cpp:1:
/usr/include/c++/7/bits/stl_algo.h:3456:5: note: candidate: template<class _Tp, class _Compare> constexpr _Tp std::min(std::initializer_list<_Tp>, _Compare)
     min(initializer_list<_Tp> __l, _Compare __comp)
     ^~~
/usr/include/c++/7/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
race.cpp:90:46: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
    ans = min(ans, path[k + sum[u]] - depth[u]);
                                              ^