Submission #765704

#	Time	Username	Problem	Language	Result	Execution time	Memory
765704		vjudge1	Network (BOI15_net)	C++17	0 / 100	6 ms	11988 KiB

net

// Problem: C - Интернет связь
// Contest: Virtual Judge - IOI contest div-B
// URL: https://vjudge.net/contest/564767#problem/C
// Memory Limit: 256 MB
// Time Limit: 2000 ms
// 
// Powered by CP Editor (https://cpeditor.org)

#include <bits/stdc++.h>
using namespace std;

#define ll long long
#define pb push_back
#define sz(x) (int)x.size()
#define all(v) (v).begin(),(v).end()
#define rall(v) ((v).rbegin()), ((v).rend())
#define out(v)  for(auto& i : v) cout << i << ' ';
#define F first
#define S second
#define int long long

const ll N = 5e5 + 17;
const ll MOD = 1e9 + 7;
const string alf = "ABCDEFGHIJKLMNOPQRSTUVWXYZ";

vector <int > g[N] , ans;
int cnt = 1;

void dfs(int v , int pr = -1){
	if (g[v].size() == 1){
		ans.pb(v);
	}
	for(auto to : g[v]){
		if (pr != to){
			dfs(to , v);
		}
	}
}

void solve (){
	int n;
	cin >>n;
	for(int i = 1; i <= n - 1; i ++){
		int x , y;
		cin >> x >> y;
		g[x].pb(y);
		g[y].pb(x);
	}
	vector <int > lst;
	dfs(1);
	for(auto to : ans){
		cout <<to << " ";
	}
	cout <<(ans.size() + 1) / 2 << endl;
	if (ans.size() % 2 == 0){
		for(int i = 0; i < ans.size() / 2 ; i ++){
			cout <<ans[i] << " " << ans[ans.size() / 2 + i] << endl;
		}
	}
	else {
		for(int i = 0; i < (ans.size() + 1) / 2 - 1; i ++){
			cout <<ans[i] << " " << ans[(ans.size() + 1) / 2 + i] << endl;
		}
		cout << ans[(ans.size() + 1) / 2 - 1] << ' ' << 1 << endl;
	}
}

signed main(){
	// freopen("ones.in" , "r" , stdin) ;
	// freopen("ones.out" , "w" , stdout) ;
	ios::sync_with_stdio(false);
	cin.tie(0);
	int T = 1;
	// int cs = 1;
	// cin >>T;
	while (T --){
		// cout <<"Case " << cs ++<< ":" << endl;
		solve ();
		// cout <<endl;
	}
}

Compilation message (stderr)

net.cpp: In function 'void solve()':
net.cpp:56:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   56 |   for(int i = 0; i < ans.size() / 2 ; i ++){
      |                  ~~^~~~~~~~~~~~~~~~
net.cpp:61:20: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   61 |   for(int i = 0; i < (ans.size() + 1) / 2 - 1; i ++){
      |                  ~~^~~~~~~~~~~~~~~~~~~~~~~~~~

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