Submission #857983

#	Time	Username	Problem	Language	Result	Execution time	Memory
857983		Trisanu_Das	Village (BOI20_village)	C++17	100 / 100	86 ms	22864 KiB

Village

//AE86!!!!
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define N 100005
int n,u,v,cnt=1,h1[N],h2[N],sz[N],seq[N],lv[N],P[20][N];
ll ans1,ans2;
vector<int> adj[N];
 
void A1(int u,int p){
	for(auto v : adj[u]){
		if(v == p) continue;
		A1(v,u);
	}
	if(h1[u] == u){
		if(u == 1) swap(h1[u],h1[adj[1][0]]);
		else swap(h1[u],h1[p]);
		ans1 += 2;
	}
}
 
int size(int u,int p){
	sz[u] = 1;
	for(auto v : adj[u]) if(v != p) sz[u] += size(v,u);
	return sz[u];
}
 
int find_cen(int u,int p,int all){
	for(auto v : adj[u]) if(v != p && sz[v] > n/2) return find_cen(v,u,all);
	return u;
}
 
void dfs(int u,int p,int l){
	seq[cnt++] = u;
	lv[u] = l;
	P[0][u] = p;
	for(int i=1;i<=18;i++) P[i][u] = P[i-1][P[i-1][u]];
	for(auto v : adj[u]) if(v != p) dfs(v,u,l+1);
}
 
long long dis(int u,int v){
	if(lv[u] < lv[v]) swap(u,v);
	long long diff = lv[u] - lv[v], dist = 0;
	for(int i=18;i>=0;i--) if((1<<i) & diff) dist += (1<<i), u = P[i][u];
	if(u == v) return dist;
	for(int i=18;i>=0;i--) if(P[i][u] != P[i][v]) u = P[i][u], v = P[i][v], dist += 2*(1<<i);
	return dist + 2;
}
 
void A2(int u){
	size(1,1);
	int c = find_cen(1,1,n);
	dfs(c,c,1);
	for(int i=1;i<=n;i++) h2[seq[i]] = seq[(i+n/2-1)%n+1], ans2 += dis(seq[i],h2[seq[i]]);
}
 
int main(){
	scanf("%d",&n);
	for(int i=1;i<n;i++){
		scanf("%d%d",&u,&v);
		adj[u].push_back(v), adj[v].push_back(u);
	}
	for(int i=1;i<=n;i++) h1[i] = i;
	A1(1,1);
	A2(1);
	printf("%lld %lld\n",ans1,ans2);
	for(int i=1;i<=n;i++) printf("%d ",h1[i]);
	printf("\n");
	for(int i=1;i<=n;i++) printf("%d ",h2[i]);
}

Compilation message (stderr)

Village.cpp: In function 'int main()':
Village.cpp:58:7: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   58 |  scanf("%d",&n);
      |  ~~~~~^~~~~~~~~
Village.cpp:60:8: warning: ignoring return value of 'int scanf(const char*, ...)' declared with attribute 'warn_unused_result' [-Wunused-result]
   60 |   scanf("%d%d",&u,&v);
      |   ~~~~~^~~~~~~~~~~~~~

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