Submission #258882

#	Time	Username	Problem	Language	Result	Execution time	Memory
258882		easrui	Village (BOI20_village)	C++14	100 / 100	112 ms	14072 KiB

Village

#include <bits/stdc++.h>
#define va first
#define vb second
#define all(x) (x).begin(), (x).end()
using namespace std;
typedef long long ll;
typedef pair<int,int> pii;
typedef pair<pii,int> ppi;
typedef pair<int,pii> pip;

const int MN = 1e5+5;
const int MOD = 1e9+7;
const int INF = 1e9;

ll sz[MN],N,min_ans,max_ans,cnt;
int pos[MN],ord[MN],vmin[MN],vmax[MN];
vector<int> G[MN];
bool vis[MN],done[MN];

void dfs(int s)
{
	vis[s] = 1;
	sz[s] = 1;
	for(int e:G[s]){
		if(vis[e]) continue;
		dfs(e);
		sz[s] += sz[e];
		if(done[e]) continue;
		else{
			done[s] = 1;
			swap(vmin[s],vmin[e]);
			min_ans += 2;
		}
	}
	if(s!=1) max_ans += min(sz[s],N-sz[s])*2;
	else if(!done[s]){
		swap(vmin[s],vmin[G[s][0]]);
		min_ans += 2;
	}
}

void get(int s, int p)
{
	ord[++cnt] = s;
	pos[s] = cnt;
	for(int e:G[s]){
		if(e==p) continue;
		get(e,s);
	}
}

int main()
{
    ios_base::sync_with_stdio(0),cin.tie(0);
    cin >> N;
    for(int i=1; i<N; i++){
    	int s,e;
    	cin >> s >> e;
    	G[s].push_back(e);
    	G[e].push_back(s);
    }
    for(int i=1; i<=N; i++) vmin[i] = i;
    dfs(1);

	int s = 1, p = 0;
	while(1){
		bool ch = 0;
		for(int e:G[s]){
			if(e==p) continue;
			if(sz[e]>N/2){
				ch = 1;
				p = s;
				s = e;
				break;
			}
		}
		if(!ch) break;
	}
	ord[0] = s;
	pos[s] = 0;
	for(int e:G[s]) get(e,s);
	for(int i=1; i<=N; i++){
		vmax[i] = ord[(pos[i]+N/2)%N];
	}

    cout << min_ans << ' ' << max_ans << '\n';
    for(int i=1; i<=N; i++) cout << vmin[i] << ' ';
   	cout << '\n';
   	for(int i=1; i<=N; i++) cout << vmax[i] << ' ';
}

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