Submission #366745

#	Time	Username	Problem	Language	Result	Execution time	Memory
366745		arnold518	Village (BOI20_village)	C++14	100 / 100	177 ms	29864 KiB

Village

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;

const int MAXN = 1e5;

int N;
vector<int> adj[MAXN+10];

ll ans1, ans2;
int memo[MAXN+10];
int P1[MAXN+10], P2[MAXN+10];

int dp1[MAXN+10], dp2[MAXN+10];
int L[MAXN+10], cnt;
void dfs(int now, int bef)
{
	L[now]=++cnt;
	int chd=0;

	bool flag=false;
	pii p={987654321, -1};
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		chd++;
		dfs(nxt, now);
		dp1[now]+=min(dp1[nxt]+1, dp2[nxt]);
		if(dp1[nxt]+1<=dp2[nxt])
		{
			dp2[now]+=dp1[nxt]+1;
			flag=true;
		}
		else
		{
			dp2[now]+=dp2[nxt];
			p=min(p, {dp1[nxt]+1-dp2[nxt], nxt});
		}
	}
	if(!flag)
	{
		dp2[now]+=p.first;
		memo[now]=p.second;
	}
	if(chd==0) dp2[now]=987654321;
}

struct UF
{
	int par[MAXN+10];
	int Find(int x)
	{
		if(par[x]==x) return x;
		return par[x]=Find(par[x]);
	}
	void Union(int x, int y)
	{
		x=Find(x); y=Find(y);
		par[x]=y;
	}
}uf;

void dfs2(int now, int bef, int col)
{
	if(col==1)
	{
		for(auto nxt : adj[now])
		{
			if(nxt==bef) continue;
			if(dp1[nxt]+1<=dp2[nxt])
			{
				uf.Union(now, nxt);
				dfs2(nxt, now, 1);
			}
			else
			{
				dfs2(nxt, now, 2);
			}
		}
	}
	else
	{
		for(auto nxt : adj[now])
		{
			if(nxt==bef) continue;
			if(dp1[nxt]+1<=dp2[nxt] || memo[now]==nxt)
			{
				uf.Union(now, nxt);
				dfs2(nxt, now, 1);
			}
			else
			{	
				dfs2(nxt, now, 2);	
			}
		}
	}
}

vector<int> V[MAXN+10];

int sz[MAXN+10];
void getsz(int now, int bef)
{
	sz[now]=1;
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		getsz(nxt, now);
		sz[now]+=sz[nxt];
	}
}

int getcen(int now, int bef)
{
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		if(sz[nxt]>N/2) return getcen(nxt, now);
	}
	return now;
}

void dfs3(int now, int bef, int d, vector<int> &V)
{
	ans2+=d*2;
	V.push_back(now);
	for(int nxt : adj[now])
	{
		if(nxt==bef) continue;
		dfs3(nxt, now, d+1, V);
	}
}

int main()
{
	scanf("%d", &N);
	for(int i=1; i<=N; i++) uf.par[i]=i;
	for(int i=1; i<N; i++)
	{
		int u, v;
		scanf("%d%d", &u, &v);
		adj[u].push_back(v);
		adj[v].push_back(u);
	}

	dfs(1, 1);
	dfs2(1, 1, 2);
	ans1=2*dp2[1];

	for(int i=1; i<=N; i++) V[uf.Find(i)].push_back(i);
	for(int i=1; i<=N; i++) sort(V[i].begin(), V[i].end(), [&](const int &p, const int &q)
	{
		return L[p]<L[q];
	});

	for(int i=1; i<=N; i++)
	{
		for(int j=0; j<V[i].size(); j++)
		{
			P1[V[i][j]]=V[i][(j+1)%V[i].size()];
		}
	}

	getsz(1, 1);
	int cen=getcen(1, 1);

	vector<vector<int>> VV, VV2;
	VV.push_back({cen});
	for(auto nxt : adj[cen])
	{
		vector<int> V;
		dfs3(nxt, cen, 1, V);
		VV.push_back(V);
	}
	VV2.resize(VV.size());

	sort(VV.begin(), VV.end(), [&](const vector<int> &p, vector<int> &q)
	{
		return p.size()<q.size();
	});

	int p;
	for(int i=VV.size()-2, j=p=VV.size()-1; i>=0; i--)
	{
		for(auto it : VV[i])
		{
			if(VV2[j].size()==VV[j].size()) j--, p--;
			VV2[j].push_back(it);
		}
	}
	for(auto it : VV[VV.size()-1])
	{
		if(VV2[p].size()==VV[p].size()) p--;
		VV2[p].push_back(it);
	}

	for(int i=0; i<VV.size(); i++)
	{
		for(int j=0; j<VV[i].size(); j++)
		{
			P2[VV[i][j]]=VV2[i][j];
		}
	}
	printf("%lld %lld\n", ans1, ans2);
	for(int i=1; i<=N; i++) printf("%d ", P1[i]); printf("\n");
	for(int i=1; i<=N; i++) printf("%d ", P2[i]); printf("\n");
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:161:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  161 |   for(int j=0; j<V[i].size(); j++)
      |                ~^~~~~~~~~~~~
Village.cpp:200:16: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<std::vector<int> >::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  200 |  for(int i=0; i<VV.size(); i++)
      |               ~^~~~~~~~~~
Village.cpp:202:17: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  202 |   for(int j=0; j<VV[i].size(); j++)
      |                ~^~~~~~~~~~~~~
Village.cpp:208:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  208 |  for(int i=1; i<=N; i++) printf("%d ", P1[i]); printf("\n");
      |  ^~~
Village.cpp:208:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  208 |  for(int i=1; i<=N; i++) printf("%d ", P1[i]); printf("\n");
      |                                                ^~~~~~
Village.cpp:209:2: warning: this 'for' clause does not guard... [-Wmisleading-indentation]
  209 |  for(int i=1; i<=N; i++) printf("%d ", P2[i]); printf("\n");
      |  ^~~
Village.cpp:209:48: note: ...this statement, but the latter is misleadingly indented as if it were guarded by the 'for'
  209 |  for(int i=1; i<=N; i++) printf("%d ", P2[i]); printf("\n");
      |                                                ^~~~~~
Village.cpp:139:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  139 |  scanf("%d", &N);
      |  ~~~~~^~~~~~~~~~
Village.cpp:144:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  144 |   scanf("%d%d", &u, &v);
      |   ~~~~~^~~~~~~~~~~~~~~~

• Subtask 1: 12 / 12
• Subtask 2: 38 / 38
• Subtask 3: 50 / 50