Submission #1127010

#	Time	Username	Problem	Language	Result	Execution time	Memory
1127010		Agageldi	Network (BOI15_net)	C++20	18 / 100	2096 ms	28904 KiB

net

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define N 600005
#define ff first
#define ss second
#define pb push_back
#define sz(s) (int)s.size()
#define rep(c, a, b) for(c = a; c <= b; c++)
 
//mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
 
ll n, t, out[N],vip[3000][3000], cnt;
vector <int> v[N], ans;

void find(int x) {
	out[x] = 1;
	cnt++;
	for(auto i:v[x]) {
		if(vip[x][i] == 1 || out[i] == 1) continue;
		find(i);
	}
}
void solve() {
	bool tr = 0;
	for(int i = 1; i <= n; i++) {
		for(auto j:v[i]) {
			for(int k = 1; k <= n; k++) {
				out[k] = 0;
			}
			vip[i][j] = vip[j][i] = 1;
			cnt = 0;
			find(1);
			vip[i][j] = vip[j][i] = 0;
			if(cnt != n) {
				tr = 1;
				break;
			}
		}
		if(tr) break;
	}
	if(!tr) {
		cout << (sz(ans) + 1) / 2 << '\n';
		for(int i = 0;i<sz(ans) - 1;i++) {
			cout << ans[i] << " " << ans[i+1] << '\n';
			i++;
		}
		if(sz(ans)%2) {
			cout << ans[0] << " " << ans[sz(ans) - 1] << '\n';
		}
		exit(0);
	}
}

int main () {
	ios::sync_with_stdio(0);cin.tie(0);
	cin >> n;
	for(int i = 1; i < n; i++) {
		int x, y;
		cin >> x >> y;
		v[x].pb(y);
		v[y].pb(x);
	}
	for(int i = 1;i<=n;i++) {
		if(sz(v[i]) == 1) ans.pb(i);
	}
	do{
		for(int i = 0;i<sz(ans) - 1;i++) {
			v[ans[i]].pb(ans[i+1]);
			v[ans[i+1]].pb(ans[i]);
			i++;
		}
		if(sz(ans)%2) {
			v[ans[0]].pb(ans[sz(ans) - 1]);
			v[ans[sz(ans) - 1]].pb(ans[0]);
		}
		solve();
		for(int i = 0;i<sz(ans) - 1;i++) {
			v[ans[i]].pop_back();
			v[ans[i+1]].pop_back();
			i++;
		}
		if(sz(ans)%2) {
			v[ans[0]].pop_back();
			v[ans[sz(ans) - 1]].pop_back();
		}
	}while(next_permutation(ans.begin(),ans.end()));
}

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