Submission #953495

#	Time	Username	Problem	Language	Result	Execution time	Memory
953495		koukirocks	Village (BOI20_village)	C++17	12 / 100	417 ms	600 KiB

Village

#include <bits/stdc++.h>
#define speed ios_base::sync_with_stdio(0); cin.tie(0)
#define all(x) (x).begin(),(x).end()
#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) {
//	cout<<v<<" "<<p<<"\n"<<flush;
	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() {
	speed;
	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;
		}
		{
//			for (int i=1;i<=n;i++) {
//				cout<<perm[i]<<" ";
//			}
//			cout<<"\n"<<flush;
			int ttl=0;
			for (int i=1;i<=n;i++) {
				ttl+=dfs(i,0,0,perm[i]);
			}
//			cout<<ttl<<" ttl\n"<<flush;
			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";
	return 0;
}

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