Submission #977298

#	Time	Username	Problem	Language	Result	Execution time	Memory
977298		aeg	Village (BOI20_village)	C++14	12 / 100	418 ms	600 KiB

Village

#include <bits/stdc++.h>
#define F first
#define S second
#pragma GCC optimize("O3")
#pragma GCC target("avx2")

namespace{using namespace std;}
typedef long long ll;
typedef double db;
typedef long double ldb;
typedef pair<int,int> pii;
typedef pair<ll,ll> pll;

const ll MAX=10+10,P=1e9+7;
const ll INF=0x3f3f3f3f,oo=0x3f3f3f3f3f3f3f3f;
const ldb eps=1e-6;

int n;
vector<int> G[MAX];

int dfs(int v,int p,int d,int tar) {
	if (v==tar) return d;
	for (int i:G[v]) {
		if (i==p) continue;
		int rlt=dfs(i,v,d+1,tar);
		if (rlt!=-1) return rlt;
	}
	return -1;
}

int main() {
	cin.tie(0)->sync_with_stdio(0);
	cin>>n;
	for (int i=1;i<n;i++) {
		int a,b;
		cin>>a>>b;
		G[a].push_back(b);
		G[b].push_back(a);
	}
	int perm[11]={0,1,2,3,4,5,6,7,8,9,10};
	int ans[11];
	int ans2[11];
	int maxx=0;
	int minn=INF;
	do {
		for (int i=1;i<=n;i++) {
			if (perm[i]==i) goto die;
		}
		{
			int ttl=0;
			for (int i=1;i<=n;i++) {
				ttl+=dfs(i,0,0,perm[i]);
			}
			if (ttl>maxx) {
				maxx=ttl;
				for (int i=1;i<=n;i++) {
					ans[i]=perm[i];
				}
			}
			if (ttl<minn) {
				minn=ttl;
				for (int i=1;i<=n;i++) {
					ans2[i]=perm[i];
				}
			}
		}
		die:
		;
	} while (next_permutation(perm+1,perm+n+1));
	cout<<minn<<" "<<maxx<<"\n";
	for (int i=1;i<=n;i++) {
		cout<<ans2[i]<<" ";
	}
	cout<<"\n";
	for (int i=1;i<=n;i++) {
		cout<<ans[i]<<" ";
	}
	cout<<"\n";
}

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