Submission #394658

#	Time	Username	Problem	Language	Result	Execution time	Memory
394658		armanmohammadi	Network (BOI15_net)	C++14	100 / 100	786 ms	53100 KiB

net

/*
 _________        .---"""      """---.
:______.-':      :  .--------------.  :
| ______  |      | :                : |
|:______B:|      | |  Little Error: | |
|:______B:|      | |                | |
|:______B:|      | |  Power not     | |
|         |      | |  found.        | |
|:_____:  |      | |                | |
|    ==   |      | :                : |
|       O |      :  '--------------'  :
|       o |      :'---...______...---'
|       o |-._.-i___/'             \._
|'-.____o_|   '-.   '-...______...-'  `-._
:_________:      `.____________________   `-.___.-.
                 .'.eeeeeeeeeeeeeeeeee.'.      :___:
    fsc        .'.eeeeeeeeeeeeeeeeeeeeee.'.
              :____________________________:
*/




//in the name of god
//if you read this code please search about imam hussain
#include<bits/stdc++.h>

using namespace std;

typedef long long ll;

#define pb push_back
#define endl "\n"
#define X first
#define Y second
#define pii pair<int,int>
#define migmig ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define read freopen("input.txt", "r", stdin);freopen("output.txt", "w", stdout)

const int maxn=5e5+5;
const int mod=1e9+7;
const int inf=1e9;
const int del=728729;

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));}


int n ;
int deg ;
int DD[maxn];
vector<int> B ;
vector<int> adj[maxn];
int cnt ;
void dfs(int v, int P = 0){
	DD[v] = deg++;
	for(auto u : adj[v]){
		if(u == P){
			continue;
		} 
		dfs(u, v);
	}
}
 
bool cmp(int i, int j){
	return DD[i] < DD[j];
}
 
int main(){
	cin >> n ;
	int root =1 ;
	for(int i = 1; i < n ;i ++){
		int x ;
		int y ;
		cin >> x >> y ;
		adj[x].push_back(y) ;
		adj[y].push_back(x) ;
	}
	for(int i = 1; i <= n; i ++){
		if(adj[i].size() > 1){
			root = i;
		}
		if(adj[i].size() == 1){
			B.pb(i);
			cnt++;
		}
	}
	dfs(root);
	sort(B.begin() , B.end() , cmp);
	cout<<(cnt + 1 ) / 2 <<endl ; 
	cnt = (cnt + 1) / 2 ; 
	for(int i = 0 ; i + cnt < B.size() ; i ++ ){
		cout<<B[i] <<" " << B[i + cnt] << endl ; 
	}
	if(B.size() % 2 == 1){
		cout<<B[cnt-1] <<" " << B[0] << endl ; 
	}
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:91:26: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   91 |  for(int i = 0 ; i + cnt < B.size() ; i ++ ){
      |                  ~~~~~~~~^~~~~~~~~~

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