oj.uz

Submission #951416

# Submission time Handle Problem Language Result Execution time Memory
951416 2024-03-21T23:23:07 Z Doncho_Bonboncho Network (BOI15_net) C++14
0 / 100
 12 ms 25688 KB 
#include <bits/stdc++.h>
using namespace std;

template< class T, class T2 > inline bool chkmin( T& a, const T2& b ){ return a > b ? a = b, 1 : 0; }
template< class T, class T2 > inline bool chkmax( T& a, const T2& b ){ return a < b ? a = b, 1 : 0; }

#ifndef LOCAL
#define cerr if( false )cerr
#endif

#define out(x) #x << " = " << x << "  "

typedef long long ll;

const int MAX_N = 1e6 + 42;
const ll mod = 1e9 + 7;

std::vector< int > v[MAX_N];
int par[MAX_N];

void dfs( int x, int p = -1 ){
	par[x] = p;
	for( auto j : v[x] ){
		if( j == p ) continue;
		dfs( j, x );
	}
}
int main (){

#ifndef LOCAL
	std::ios_base::sync_with_stdio( false ); std::cin.tie( NULL ); std::cout.tie( NULL );
#endif

	int n;
	std::cin >> n;

	for( int i=0 ; i < n-1 ; i++ ){
		int a, b;
		std::cin >> a >> b;
		a--; b--;
		v[a].push_back( b );
		v[b].push_back( a );
	}
	
	int st = 0;
	for( int i=0 ; i < n ; i++ ){
		if( v[i].size() == 1){
			st = i;
			break;
		}
	}

	dfs( st );
	std::vector< std::pair< int ,int > > leaves;
	for( int i=0 ; i < n ; i++ ){
		if( v[i].size() == 1 ) leaves.push_back({ par[i], i });
	}

	std::sort( leaves.begin(), leaves.end() );

	ll nas = leaves.size() / 2;
	if( leaves.size() & 1 ){
		nas ++;
		std::cout << nas << endl;
		std::cout << leaves.back().second +1 << " " << leaves[0].second +1 << endl;
		leaves.pop_back();
	}else{
		std::cout << nas << endl;
	}

	for( int i=0 ; i < leaves.size()/ 2 ; i ++ ){
		std::cout << leaves[i].second +1 << " " << leaves[ leaves.size() -1 -i ].second +1 << endl;
	}

	return 0;
}

Compilation message

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

Subtask #1
0 / 18.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25432 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 5 ms 25436 KB Output is correct
5 Correct 6 ms 25436 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25688 KB Output is correct
9 Correct 5 ms 25436 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 6 ms 25432 KB Output is correct
12 Incorrect 5 ms 25436 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25432 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 5 ms 25436 KB Output is correct
5 Correct 6 ms 25436 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25688 KB Output is correct
9 Correct 5 ms 25436 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 6 ms 25432 KB Output is correct
12 Incorrect 5 ms 25436 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 25432 KB Output is correct
2 Correct 7 ms 25436 KB Output is correct
3 Correct 6 ms 25436 KB Output is correct
4 Correct 5 ms 25436 KB Output is correct
5 Correct 6 ms 25436 KB Output is correct
6 Correct 6 ms 25436 KB Output is correct
7 Correct 5 ms 25436 KB Output is correct
8 Correct 6 ms 25688 KB Output is correct
9 Correct 5 ms 25436 KB Output is correct
10 Correct 8 ms 25436 KB Output is correct
11 Correct 6 ms 25432 KB Output is correct
12 Incorrect 5 ms 25436 KB Breaking single line is causing network to disconnect.
13 Halted 0 ms 0 KB -