Submission #802397

#	Time	Username	Problem	Language	Result	Execution time	Memory
802397		parsadox2	Village (BOI20_village)	C++14	100 / 100	122 ms	30120 KiB

Village

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

const int maxn = 1e5 + 10;
int n , st[maxn] , fn[maxn] , dp[2][maxn] , par[2][maxn] , sz[maxn] , ar[maxn] , br[maxn] , pos[maxn];
vector <int> trav , adj[maxn] , child[maxn];

void dfs(int v , int p = -1)
{
	st[v] = trav.size();
	sz[v] = 1;
	trav.push_back(v);
	for(auto u : adj[v])  if(u != p)
	{
		dfs(u , v);
		sz[v] += sz[u];
	}
	fn[v] = trav.size();
}

bool cmp(int a , int b)
{
	return dp[1][a] - dp[0][a] < dp[1][b] - dp[0][b];
}

void solve(int v , int p = -1)
{
	bool leaf = true;
	int sum = 0;
	for(auto u : adj[v])  if(u != p)
	{
		leaf = false;
		solve(u , v);
		child[v].push_back(u);
		sum += dp[0][u];
	}
	if(leaf)
	{
		dp[1][v] = 0;
		dp[0][v] = maxn << 2;
		pos[v] = v;
		return;
	}
	sort(child[v].begin() , child[v].end() , cmp);
	//cout << v << " " << p << " : " << endl;
	//for(auto u : child[v])
	//	cout << u << " " << dp[0][u] << " " << dp[1][u] << endl;
	//cout << endl;
	int fsum = sum;
	dp[1][v] = sum;
	par[1][v] = 0;
	pos[v] = v;
	fsum += (dp[1][child[v][0]] - dp[0][child[v][0]]);
	//cout << fsum << endl;
	if(fsum + 2 < dp[1][v])
	{
		par[1][v] = 1;
		dp[1][v] = fsum + 2;
		pos[v] = pos[child[v][0]];
	}
	//cout << dp[1][v] << "!" << endl;
	for(int i = 1 ; i < child[v].size() ; i++)
	{
		int now = child[v][i];
		fsum += (dp[1][now] - dp[0][now]);
		if(fsum + 2 * (i + 1) < dp[1][v])
		{
			dp[1][v] = fsum + 2 * (i + 1);
			par[1][v] = i + 1;
			pos[v] = v;
		}
	}
	//cout << "SALAM" << endl;
	//cout << v << " " << p << endl;
	fsum = sum + dp[1][child[v][0]] - dp[0][child[v][0]];
	dp[0][v] = fsum + 2;
	par[0][v] = 1;
	for(int i = 1 ; i < child[v].size() ; i++)
	{
		//cout << i << endl;
		int now = child[v][i];
		fsum += (dp[1][now] - dp[0][now]);
		if(fsum + 2 * (i + 1) < dp[0][v])
		{
			dp[0][v] = fsum + 2 * (i + 1);
			par[0][v] = i + 1;
		}
	}
	//cout << v << " " << dp[0][v] << " " << dp[1][v] << endl;
	//if(v == 5)
	//	dp[1][v] = 2;
}

void Build(int v , int ty)
{
	//cout << v << " " << ty << " " << child[v].size() << endl;
	if(child[v].size() == 0)
		return;
	for(int i = 0 ; i < par[ty][v] ; i++)
		Build(child[v][i] , 1);
	for(int i = par[ty][v] ; i < child[v].size() ; i++)
		Build(child[v][i] , 0);
	//cout << v << " " << ty << endl;
	for(int i = 0 ; i + 1 < par[ty][v] ; i++)
		ar[child[v][i]] = pos[child[v][i + 1]];
	if(ty == 1)
	{
		if(par[ty][v] == 1)
		{
			ar[child[v][0]] = v;
		}
		else if(par[ty][v] != 0)
			ar[child[v][par[ty][v] - 1]] = pos[child[v][0]];		
	}
	else
	{
		ar[v] = pos[child[v][0]];
		ar[child[v][par[ty][v] - 1]] = v;
	}
}

signed main()
{
	ios::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for(int i = 0 ; i < n - 1 ; i++)
	{
		int v , u;  cin >> v >> u;
		adj[v].push_back(u);
		adj[u].push_back(v);
	}
	dfs(1);
	//cout << "DFSED" << endl;
	solve(1);
	//cout << "SOLVED" << endl;
	Build(1 , 0);
	//cout << "BUILt" << endl;
	int lar = 0 , sma = dp[0][1];
	for(int i = 2 ; i <= n ; i++)
		lar += min(sz[i] , n - sz[i]) * 2;
	for(int i = 1 ; i <= n ; i++)
		br[i] = trav[(st[i] + (n / 2)) % n];
	cout << sma << " " << lar << endl;
	for(int i = 1 ; i <= n ; i++)
		cout << ar[i] << " ";
	cout << endl;
	for(int i = 1 ; i <= n ; i++)
		cout << br[i] << " ";
	cout << endl;
	return 0;
}

Compilation message (stderr)

Village.cpp: In function 'void solve(long long int, long long int)':
Village.cpp:63:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |  for(int i = 1 ; i < child[v].size() ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~
Village.cpp:79:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   79 |  for(int i = 1 ; i < child[v].size() ; i++)
      |                  ~~^~~~~~~~~~~~~~~~~
Village.cpp: In function 'void Build(long long int, long long int)':
Village.cpp:102:29: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
  102 |  for(int i = par[ty][v] ; i < child[v].size() ; i++)
      |                           ~~^~~~~~~~~~~~~~~~~

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