Submission #1093131

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
1093131	2024-09-26T02:15:48 Z	Jawad_Akbar_JJ	Village (BOI20_village)	C++17	Compilation error	0 ms	0 KB

Village

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
const int N = 1e5 + 10;
vector<int> nei[N], lst;
int Num[N], Num2[N], ch[N];
long long Mx = 0, Mn = 0, n;

void dfs(int u, int p, int c = 0){
	ch[u] = 1;
	for (int i : nei[u]){
		if (i == p)
			continue;
		dfs(i, u, c);
		ch[u] += ch[i];
		Mx += min(n - ch[i], ch[i]);
	}
	if (c == 0)
		return;
	vector<int> vec = {u};
	for (int i : nei[u]){
		if (i == p)
			continue;
		if (Num2[i] == i or (u == 1 and vec.size() == 1)){
			int k = Num2[i];
			Num2[i] = vec.back();
			vec.push_back(k);
		}
	}
	Num2[u] = vec.back();
	Mn += (vec.size() - 1) * 2;
}

int find_cent(int u, int p){
	for (int i : nei[u])
		if (i != p and ch[i] * 2 > ch[1])
			return find_cent(i, u);
	return u;
}

void get(int u, int p){
	for (int i : nei[u])
		if (i != p)
			get(i, u);
	lst.push_back(u);
}
vector<int> get(int a, int b, int c){
	lst.clear();
	get(a, b);
	return lst;
}

void solve(){
	dfs(1, 1, 1);
	int rt = find_cent(1, 1), ind = 0;
	dfs(rt, rt);

	vector<pair<int,int>> vec;
	for (int i : nei[rt])
		vec.push_back({ch[i], i});
	sort(rbegin(vec), rend(vec));

	vector<int> Vec =get(vec[0].second, rt, 1);
	for (int i=1;i<vec.size();i++){
		vector<int> v = get(vec[i].second, rt, 1);
		for (int j : v)
			Num[j] = Vec[ind++], Vec.push_back(j);
	}

	Vec.push_back(rt);
	Num[rt] = Vec[ind++];
	get(vec[0].second, rt, 1);
	for (int i : lst)
		Num[i] = Vec[ind++];
}

int main(){
	cin>>n;

	for (int i=1, a, b;i<n;i++){
		cin>>a>>b;
		nei[a].push_back(b);
		nei[b].push_back(a);
	}
	if (n == 1){
		cout<<1 / 0;
		return 0;
	}

	solve();

	cout<<Mn<<" "<<Mx<<'\n';
	for (int i=1;i<=n;i++)
		cout<<Num2[i]<<' ';
	cout<<'\n';
	for (int i=1;i<=n;i++)
		cout<<Num[i]<<' ';
	cout<<'\n';
}

Compilation message

Village.cpp: In function 'void dfs(int, int, int)':
Village.cpp:18:29: error: no matching function for call to 'min(long long int, int&)'
   18 |   Mx += min(n - ch[i], ch[i]);
      |                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from Village.cpp:1:
/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:
Village.cpp:18:29: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   18 |   Mx += min(n - ch[i], ch[i]);
      |                             ^
In file included from /usr/include/c++/10/bits/char_traits.h:39,
                 from /usr/include/c++/10/ios:40,
                 from /usr/include/c++/10/ostream:38,
                 from /usr/include/c++/10/iostream:39,
                 from Village.cpp:1:
/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:
Village.cpp:18:29: note:   deduced conflicting types for parameter 'const _Tp' ('long long int' and 'int')
   18 |   Mx += min(n - ch[i], ch[i]);
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from Village.cpp:3:
/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:
Village.cpp:18:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   18 |   Mx += min(n - ch[i], ch[i]);
      |                             ^
In file included from /usr/include/c++/10/algorithm:62,
                 from Village.cpp:3:
/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:
Village.cpp:18:29: note:   mismatched types 'std::initializer_list<_Tp>' and 'long long int'
   18 |   Mx += min(n - ch[i], ch[i]);
      |                             ^
Village.cpp: In function 'void solve()':
Village.cpp:66:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::pair<int, int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   66 |  for (int i=1;i<vec.size();i++){
      |               ~^~~~~~~~~~~
Village.cpp: In function 'int main()':
Village.cpp:88:11: warning: division by zero [-Wdiv-by-zero]
   88 |   cout<<1 / 0;
      |         ~~^~~