Submission #1087552

#	Time	Username	Problem	Language	Result	Execution time	Memory
1087552		freedommo33	Village (BOI20_village)	C++17	12 / 100	48 ms	604 KiB

Village

#include <bits/stdc++.h>
typedef long long ll;
constexpr int M = 25;
using namespace std;
vector<vector<int>> g(M);
int odl[M][M]; 
int makstab[M];
int mintab[M];
void bfs(int v){
	queue<int> q;
	q.push(v);
	while(!q.empty()){
		int p = q.front();
		q.pop();
		for(auto i:g[p]) if(odl[v][i] == 0 && i != v){
			odl[v][i] = odl[v][p] + 1;
			q.push(i);
		}
	}
}

int main(){
	cin.tie(0)->sync_with_stdio(0);
	int n;
	cin>>n;
	int mini = 21376969;
	int maks = 0;
	for(int i=1; i<n; i++){
		int a, b;
		cin>>a>>b;
		g[a].push_back(b);
		g[b].push_back(a);
	}
	for(int i=1; i<=n; i++) bfs(i);
	vector<int> v;
	for(int i=1; i<=n; i++) v.push_back(i);
	do{
		bool czy = 0;
		for(int i=1; i<=n; i++) if(v[i-1] == i) czy = 1;
		if(czy==1) continue;
		int akt = 0;
		for(int i=1; i<=n; i++) akt += odl[v[i-1]][i];
		if(mini > akt){
			mini = akt;
			for(int i=1; i<=n; i++) mintab[i] = v[i-1];
		}
		if(maks < akt){
			maks = akt;
			for(int i=1; i<=n; i++) makstab[i] = v[i-1];
		}
	}while(next_permutation(v.begin(), v.end()));
	cout<<mini<<" "<<maks<<endl;
	for(int i=1; i<=n; i++) cout<<mintab[i]<<" ";
	cout<<endl;
	for(int i=1; i<=n; i++) cout<<makstab[i]<<" ";
	cout<<endl;
	return 0;
}

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