Submission #1225012

#	Time	Username	Problem	Language	Result	Execution time	Memory
1225012		jellybean	Network (BOI15_net)	C++20	18 / 100	1885 ms	436 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define pb push_back
#define dd(x) cout<<#x<<" is "<<x<<endl;
#define dd2(x,y) cout<<#x<<" is "<<x<<" "<<#y<<" is "<<y<<endl;
#define dl(x) cout<<#x<<" is "<<endl; for(int i=1; i<9; i++) cout<<x[i]<<' '; cout<<endl;
#define fi first
#define se second
typedef pair<int,int> pii;

const int N = 11;
vector<int>adj[N];
int p[N], r[N];

int fs(int x){
	if(p[x] == x) return x;
	else return p[x] = fs(p[x]);
}

void merge(int a, int b){
	a = fs(a), b = fs(b);
	if(r[a] < r[b]) swap(a,b);
	p[b] = a;
	if(r[a] == r[b]) r[a]++;
}

vector<pii>edges;

signed main(){
	ios::sync_with_stdio(0); cin.tie(0);
	
	int n; cin>>n;
	for(int i=0; i<n-1; i++){
		int a,b; cin>>a>>b;
		adj[a].pb(b);
		adj[b].pb(a);
		edges.pb({a,b});
	}
	
	vector<int>leaves;
	for(int i=1; i<=n; i++){
		if(adj[i].size() == 1) leaves.pb(i);
	}
	
	vector<int>v;
	for(int i=1; i<=n; i++) v.pb(i);
	
	int ans = LLONG_MAX;
	vector<int>save;
	do{
		bool f = 0;
		int cnt = 0;
		for(int e=0; e<n-1; e++){ //edge to not take
			
			int cc = 0;
			for(int i=1; i<=n; i++) p[i] = i, r[i] = 0;
			for(int i=0; i<leaves.size(); i++){
				int u = leaves[i];
				int c = v[i];
				
				if(fs(u) == fs(c)) continue;
				cc++;
				
				merge(u,c);
			}	
			
			cnt = cc;
			
			for(int j=0; j<n-1; j++){
				if(j == e) continue;
				merge(edges[j].fi, edges[j].se);
			}
			
			if(fs(edges[e].fi) != fs(edges[e].se)) {f=1; break;}
		}
		if(f == 0 and cnt < ans){
			ans = cnt;
			save = v;
		}
		
	} while(next_permutation(v.begin(), v.end()));
	
	
	cout<<ans<<'\n';
	
	for(int i=1; i<=n; i++) p[i] = i, r[i] = 0;
	
	for(int i=0; i<leaves.size(); i++){
		int u = leaves[i];
		int c = save[i];
		
		if(fs(u) == fs(c)) continue;
		merge(u,c);
		cout<<u<<' '<<c<<'\n';
	}	
			
	
	
	return 0;
}

• Subtask 1: 18 / 18
• Subtask 2: 0 / 45
• Subtask 3: 0 / 37