Submission #306498

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
306498	2020-09-25T17:45:26 Z	tengiz05	Dreaming (IOI13_dreaming)	C++17	Compilation error	0 ms	0 KB

dreaming

#include "dreaming.h"
#include <bits/stdc++.h>
using namespace std;
int n;
const int N = 1e5+5;
bool used[N];
int depth[N];
int dp[N];
vector<pair<int, int>> edges[N];
vector<int> a[N];
// dfs for calculating dp. (dp[i] - maximum depth)
void dfs(int u, int p){
	used[u] = true;
	dp[u] = 0;
	a[u].push_back(0);a[u].push_back(0);
	for(auto X : edges[u]){
		int v = X.first;
		int cost = X.second;
		if(v == p)continue;
		dfs(v, u);
		dp[u] = max(dp[u], dp[v]+cost);
		a[u].push_back(dp[v]+cost);
	}
	sort(a[u].begin(), a[u].end());
	reverse(a[u].begin(), a[u].end());
}
 
//dfs for rerooting
int mn;
void dfs2(int u, int p, int T){
	int dpu = dp[u];
	for(auto X : edges[u]){
		int v = X.first;
		int cost = X.second;
		if(v == p)continue;
		int tmp = dp[v];
		if(dp[v]+cost == a[u][0])dp[u] = a[u][1];
		if(u != p)dp[u] = max(dp[u], dp[p] + T);
		dp[v] = max(dp[v], dp[u] + cost);
		mn = min(mn, dp[v]);
		dfs2(v, u, cost);
		dp[v] = tmp;
		dp[u] = dpu;
	}
}
 
//calculate best center for the tree
int calculate_center(int u){
	dfs(u, u);
	mn = dp[u];
	dfs2(u, u ,0);
	return mn;
}
int travelTime(int _N, int M, int L, int A[], int B[], int T[]) {
	n = _N;
	for(int i=0;i<M;i++){
		edges[A[i]].push_back({B[i], T[i]});
		edges[B[i]].push_back({A[i], T[i]});
	}
	vector<int> v;
	for(int i=0;i<n;i++){
		if(!used[i]){
			v.push_back(calculate_center(i));
		}
	}v.push_back(0);
	sort(v.begin(), v.end());
	reverse(v.begin(), v.end());
	if(v.size() == 0){
		return 0;
	}
	else if(v.size() == 1){
		return a[0][0] + a[0][1];
	}
	else {
		int m = 0;
		for(int i=0;i<n;i++){
			m = max(m, a[i][0]+a[i][1]);
		}
		return max(max(v[0]+v[1]+L), m);
	}
}

Compilation message

dreaming.cpp: In function 'int travelTime(int, int, int, int*, int*, int*)':
dreaming.cpp:79:29: error: no matching function for call to 'max(__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type)'
   79 |   return max(max(v[0]+v[1]+L), m);
      |                             ^
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 dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:222:5: note: candidate: 'template<class _Tp> constexpr const _Tp& std::max(const _Tp&, const _Tp&)'
  222 |     max(const _Tp& __a, const _Tp& __b)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:222:5: note:   template argument deduction/substitution failed:
dreaming.cpp:79:29: note:   candidate expects 2 arguments, 1 provided
   79 |   return max(max(v[0]+v[1]+L), m);
      |                             ^
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 dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algobase.h:268:5: note: candidate: 'template<class _Tp, class _Compare> constexpr const _Tp& std::max(const _Tp&, const _Tp&, _Compare)'
  268 |     max(const _Tp& __a, const _Tp& __b, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algobase.h:268:5: note:   template argument deduction/substitution failed:
dreaming.cpp:79:29: note:   candidate expects 3 arguments, 1 provided
   79 |   return max(max(v[0]+v[1]+L), m);
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3456:5: note: candidate: 'template<class _Tp> constexpr _Tp std::max(std::initializer_list<_Tp>)'
 3456 |     max(initializer_list<_Tp> __l)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3456:5: note:   template argument deduction/substitution failed:
dreaming.cpp:79:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   79 |   return max(max(v[0]+v[1]+L), m);
      |                             ^
In file included from /usr/include/c++/9/algorithm:62,
                 from /usr/include/x86_64-linux-gnu/c++/9/bits/stdc++.h:65,
                 from dreaming.cpp:2:
/usr/include/c++/9/bits/stl_algo.h:3462:5: note: candidate: 'template<class _Tp, class _Compare> constexpr _Tp std::max(std::initializer_list<_Tp>, _Compare)'
 3462 |     max(initializer_list<_Tp> __l, _Compare __comp)
      |     ^~~
/usr/include/c++/9/bits/stl_algo.h:3462:5: note:   template argument deduction/substitution failed:
dreaming.cpp:79:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'int'
   79 |   return max(max(v[0]+v[1]+L), m);
      |                             ^