Submission #394608

#	Time	Username	Problem	Language	Result	Execution time	Memory
394608		RohamIzadidoost	Network (BOI15_net)	C++14	100 / 100	792 ms	45136 KiB

net

#pragma GCC optimize("Ofast,unroll-loops,fast-math")
#include<bits/stdc++.h>
using namespace std;
typedef long long ll ;
#define pll pair<ll , ll >
#define all(x) (x).begin(),(x).end()
#define SZ(x) (ll)(x).size()
#define X   first
#define Y   second
#define mp  make_pair
#define pii pair<int , int>
#define vec vector
#define file_io freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout);
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
#define pb push_back
#define ld long double
// BIG p : 1000000000000037 , 100000000003
ll poww(ll a, ll b, ll md) {
    return (!b ? 1 : (b & 1 ? a * poww(a * a % md, b / 2, md) % md : poww(a * a % md, b / 2, md) % md));
}
const int maxn = 5000*100+5 ;
const ll inf = 9223372036854775807 ;
const ll mod = 1e9 + 7 ;
const int lg = 20 ;
int n , nl , st[maxn]  , cnt , mark[maxn];
vec<pii> l ; 
vec<int> adj[maxn] ; 
void dfs(int v ){
	st[v] = cnt ++; 
	mark[v] = 1 ; 
	for(auto u : adj[v]) if(!mark[u]) dfs(u) ;
}
int main()
{
	migmig ;
	cin>>n ; 
	for(int i = 1 ; i < n ; i ++ ){
		int u , v ; 
		cin>>u>>v ; 
		adj[u].pb(v) ;
		adj[v].pb(u) ; 
	}
	for(int i = 1 ; i <= n ; i ++ ){
		if(adj[i].size() != 1){
			dfs(i) ; 
			break ; 
		}
	}
	vec<pii> v ; 
	for(int i = 1 ; i <= n ; i ++ ){
		if(SZ(adj[i]) == 1){
			nl ++ ; 
			v.pb({st[i] , i}) ; 
		}
	}
	sort(all(v)) ; 
	cout<<(nl + 1 ) / 2 <<endl ; 
	nl = (nl + 1) / 2 ; 
	for(int i = 0 ; i + nl < SZ(v) ; i ++ ){
		cout<<v[i].Y <<" " << v[i + nl].Y << endl ; 
	}
	if(SZ(v) % 2 == 1){
		cout<<v[nl-1].Y <<" " << v[0].Y << endl ; 
	}
}

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