Submission #932303

#	Time	Username	Problem	Language	Result	Execution time	Memory
932303		amirhoseinfar1385	Village (BOI20_village)	C++17	100 / 100	57 ms	19512 KiB

Village

#pragma GCC optimize("Ofast")

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ld long double
#define pb push_back //emplace_back
#define pp pop_back
#define pii pair<ll, ll> //pair<int, int>
#define all(x) (x).begin(),(x).end()
#define mp(a,b) make_pair(a , b)
#define sz(x) (ll)(x).size()
#define F first
#define S second
#define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
#define debug(x) cout << #x << " : " << x << endl << flush
#define endl '\n'
#define arr(x) array<ll , (x)>
#define yes cout << "YES\n"
#define no cout << "NO\n"
#define FAST ios_base::sync_with_stdio(0);cin.tie(0);

ll Sum(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a += b;
 return a % MOD;
}

ll Mul(ll a , ll b , ll MOD)
{
 a %= MOD;
 b %= MOD;
 a *= b;
 return a % MOD;
}

ll Pow(ll a , ll b , ll MOD)
{
   ll res = 1;
   while(b)
   {
        if((b & 1))res = Mul(res , a , MOD);
     a = Mul(a , a , MOD);
     b >>= 1;
   }
   return res;
}

ll Min(ll a , ll b)
{
   if(a > b)return b;
   return a;
}

ll Max(ll a , ll b)
{
   if(a > b)return a;
   return b;
}

ll Ceil(ll a , ll b)
{
	return a + (b-1) / b;
}

/////////////////////
//VALS
ll n;
const ll maxn = 2e5;
vector<ll> adj[maxn];
ll mx[maxn];
ll mn[maxn];
ll mx_ans, mn_ans;
ll sz[maxn];
ll centroid;
vector<ll> e;
/////////////////////
//FUNCTIONS
void dfs_mx_ans(ll u = 0, ll par = 0)
{
	sz[u] = 1;
	for(auto v : adj[u])
	{
		if(v == par)continue;
		dfs_mx_ans(v, u);
		sz[u] += sz[v];
	}
	ll x = Min(sz[u], n-sz[u]);
	mx_ans += x*2;
}

void dfs_get_centroid(ll u = 0, ll par = 0)
{
	bool flag = (n - sz[u] <= (n >> 1));
	for(auto v : adj[u])
	{
		if(v == par)continue;
		
		dfs_get_centroid(v, u);
		if(sz[v] > (n >> 1))flag = 0;
	}
	if(flag)centroid = u;
}

void dfs_get_euler(ll u = centroid, ll par = centroid)
{
	e.pb(u);
	for(auto v : adj[u])
	{
		if(v == par)continue;
		dfs_get_euler(v, u);		
	}
}

void dfs_mn(ll u = 0, ll par = 0)
{
	for(auto v : adj[u])
	{
		if(v == par)continue;
		dfs_mn(v, u);
	}
	
	if(mn[u] == u and u != 0)//swap with par
	{
		mn_ans += 2;
//		ll tmp = mn[u];
//		mn[u] = mn[par];
//		mn[par] = tmp;
		swap(mn[u], mn[par]);
	}
	
	if(mn[u] == u and u == 0)
	{
		mn_ans += 2;
//		ll tmp = mn[u];
//		mn[u] = mn[adj[u][0]];
//		mn[adj[u][0]] = tmp;
		swap(mn[u], mn[adj[u][0]]);
	}
}
/////////////////////
//SOLVE
void solve()
{
	cin >> n;
	
	For(i,n-1)
	{
		ll u, v;
		cin >> u >> v;
		u--;v--;
		
		adj[u].pb(v);
		adj[v].pb(u);	
	}
	
//	if(n == 2)
//	{
//		cout << 2 << " " << 2 << endl;
//		cout << 2 << " " << 1 << endl;
//		cout << 2 << " " << 1 << endl;
//		return;
//	}
	
	//Max
	dfs_mx_ans();
//	debug(":L");
	dfs_get_centroid();
//	debug(":L");
	dfs_get_euler();
//	debug(":L");
	
	if(n & 1)
	{
		mx[e[0]] = e[n/2]+1;
		mx[e[n/2]] = e[n-1]+1;
		mx[e[n-1]] = e[0]+1;
	}
		
	For(i,(n+1) / 2)
	{
		if(mx[e[i]])continue;
		mx[e[i]] = e[i+n/2]+1;
		mx[e[i+n/2]] = e[i]+1;
	}
	
//	cout << mx_ans << endl;
//	For(i,n)cout << mx[i] + 1 << " ";
//	cout << endl;

	//Min
	For(i,n)
		mn[i] = i;
		
	dfs_mn();
	
	
	//print
	cout << mn_ans << " " << mx_ans << endl;
	For(i,n)cout << mn[i] + 1 << " ";
	cout << endl;
	For(i,n)cout << mx[i]/* + 1 */<< " ";
	cout << endl;
}
/////////////////////
//MAIN
int main()
{
    FAST;
    ll t = 1;
//    cin >> t;
    while(t--)
    {
        solve();
    }
}
/////////////////////
/*
ZZZZZZZ     A        M     M     IIIIIII  N     N
     Z     A A      M M   M M       I     NN    N
    Z     A   A    M   M M   M      I     N N   N
   Z     AAAAAAA  M     M     M     I     N  N  N
  Z      A     A  M           M     I     N   N N
 Z       A     A  M           M     I     N    NN
ZZZZZZZ  A     A  M           M  IIIIIII  N     N  TREE
*/

Compilation message (stderr)

Village.cpp: In function 'void solve()':
Village.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
Village.cpp:151:2: note: in expansion of macro 'For'
  151 |  For(i,n-1)
      |  ^~~
Village.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
Village.cpp:184:2: note: in expansion of macro 'For'
  184 |  For(i,(n+1) / 2)
      |  ^~~
Village.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
Village.cpp:196:2: note: in expansion of macro 'For'
  196 |  For(i,n)
      |  ^~~
Village.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
Village.cpp:204:2: note: in expansion of macro 'For'
  204 |  For(i,n)cout << mn[i] + 1 << " ";
      |  ^~~
Village.cpp:17:27: warning: unnecessary parentheses in declaration of 'i' [-Wparentheses]
   17 | #define For(x, n) for(int (x) = 0 ; (x) < (n) ; (x)++)
      |                           ^
Village.cpp:206:2: note: in expansion of macro 'For'
  206 |  For(i,n)cout << mx[i]/* + 1 */<< " ";
      |  ^~~

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