Submission #1089679

#	Time	Username	Problem	Language	Result	Execution time	Memory
1089679		raczek	Village (BOI20_village)	C++17	50 / 100	83 ms	24568 KiB

Village

#include<bits/stdc++.h>
using namespace std;
#ifdef DEBUG 
auto& operator <<(auto& o, pair<auto, auto> p) {return o<<"{"<<p.first<<", "<<p.second<<"}";}
auto& operator <<(auto& o, auto x) {o<<"{"; for(auto v : x) o<<v<<", "; return o<<"}";}
#define debug(X) cerr<<"["#X"]: "<<X<<endl;
#else
#define debug(X) {}
#endif
vector<int> MinSolve(vector<vector<int> > graph)
{
	int n = graph.size();
	vector<int> result(n+1);
	for(int i=0;i<n+1;i++) result[i] = i;
	vector<int> par(n+1);
	vector<int> deg(n+1);
	queue<int> q;
	function<void(int, int)> dfs = [&](int a, int fat)
	{
		par[a] = fat;
		for(auto v : graph[a])
			if(fat != v)
				dfs(v, a);
		deg[a] = graph[a].size();
		if(a != 1 && graph[a].size() == 1) q.push(a);
	};
	dfs(1, -1);
	while(!q.empty())
	{
		int a = q.front();
		q.pop();
		if(a == 1) continue;
		if(result[a] == a)
			swap(result[a], result[par[a]]), result[0]+=2;
		deg[par[a]]--;
		if(deg[par[a]] == 1) q.push(par[a]);
	}
	if(result[1] == 1)
	{
		result[0] += 2;
		swap(result[graph[1][0]], result[1]);
	}
	return result;
}
vector<int> MaxSolve(vector<vector<int> > graph)
{
	int n = graph.size()-1;
	vector<int> Sz(n+1);
	vector<int> result(n+1);
	function<void(int, int)> getSz = [&](int a, int par)
	{
		Sz[a] = 1;
		for(auto v : graph[a])
			if(v != par)
			{
				getSz(v, a);
				Sz[a] += Sz[v];
				result[0] += Sz[v] * 2;
			}
	};
	getSz(1, -1);
	debug(Sz);
	debug(n/2);
	function<int(int, int)> getCtr = [&](int a, int par)
	{
		debug(a);
		for(auto v : graph[a])
			if(v != par)
				if(Sz[v] > n/2)
					return getCtr(v, a);
		return a;
	};
	int ctr = getCtr(1, -1);
	debug(ctr);
	result[0] = 0;
	getSz(ctr, -1);
	vector<vector<int> > grp;
	function<void(int, int)> dfs = [&](int a, int par)
	{
		grp.back().push_back(a);
		for(auto v : graph[a])
			if(v != par)
				dfs(v, a);
	};
	for(auto v : graph[ctr])
	{
		grp.push_back({});
		dfs(v, ctr);
	}
//	debug(grp);
	grp.push_back({ctr});
	sort(grp.begin(), grp.end(),[&](const vector<int>& v1,const vector<int>& v2){return v1.size()<v2.size();});
//	debug(grp);
	assert(grp[0].size() <= n/2);
//	for(auto v : grp) cerr<<v.size()<<" ";
//	cout<<endl;
	int pot = grp[1].back();
	for(int i=1;i<=n;i++) result[i] = i;
	for(int i=0;i<grp.size()-1;i++)
	{
		for(int j=i+1;j<grp.size() && grp[i].size() > 0;j++)
		{
			while(grp[i].size() > 0 && grp[j].size() > 0)
			{
				result[grp[i].back()] = grp[j].back();
				result[grp[j].back()] = grp[i].back();
				grp[i].pop_back();
				grp[j].pop_back();
			}
		}
//		cout<<grp[i].size()<<" ";
	}
//	cout<<endl;
	int k = 0;
	for(auto v : grp) k += v.size();
//	assert(k <= 1);
//	assert(grp.back().size() == 0);
	if(grp.back().size() > 0) swap(result[pot], result[grp.back()[0]]);
	//for(int i=1;i<=n;i++) assert(result[i] != i);
	return result;
}
int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	int n;
	cin>>n;
	vector<vector<int> > graph(n+1);
	for(int i=0;i<n-1;i++)
	{
		int a, b;
		cin>>a>>b;
		graph[a].push_back(b);
		graph[b].push_back(a);
	}
	vector<int> minn = MinSolve(graph);
	vector<int> maxx = MaxSolve(graph);
	cout<<minn[0]<<" "<<maxx[0]<<"\n";
	for(int i=1;i<=n;i++) cout<<minn[i]<<" ";
	cout<<"\n";
	for(int i=1;i<=n;i++) cout<<maxx[i]<<" ";
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from Village.cpp:1:
Village.cpp: In function 'std::vector<int> MaxSolve(std::vector<std::vector<int> >)':
Village.cpp:94:23: warning: comparison of integer expressions of different signedness: 'std::vector<int>::size_type' {aka 'long unsigned int'} and 'int' [-Wsign-compare]
   94 |  assert(grp[0].size() <= n/2);
      |         ~~~~~~~~~~~~~~^~~~~~
Village.cpp:99:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   99 |  for(int i=0;i<grp.size()-1;i++)
      |              ~^~~~~~~~~~~~~
Village.cpp:101:18: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  101 |   for(int j=i+1;j<grp.size() && grp[i].size() > 0;j++)
      |                 ~^~~~~~~~~~~

• Subtask 1: 6 / 12
• Subtask 2: 19 / 38
• Subtask 3: 25 / 50