Submission #969892

#	Time	Username	Problem	Language	Result	Execution time	Memory
969892		NintsiChkhaidze	Network (BOI15_net)	C++17	100 / 100	515 ms	57652 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define ull unsigned long long
#define s second
#define f first
#define pb push_back
#define left (h*2),l,(l + r)/2
#define right (h*2+1),(l+r)/2 + 1,r
#define pii pair <int,int>
#define int ll 
using namespace std;

const int N = 5e5 + 3,inf = 1e9,mod = 1e9 + 7;
int deg[N],tin[N],timer;
vector <int> v[N];

void dfs(int x,int par){
	tin[x] = ++timer;
	for (int to: v[x]){
		if (to!=par) dfs(to,x);
	}
}

signed main(){
	ios_base::sync_with_stdio(0),cin.tie(NULL),cout.tie(NULL);

	int n;
	cin>>n;

	for (int i = 1; i < n; i++){
		int a,b;
		cin>>a>>b;
		deg[a]++;
		deg[b]++;
		v[a].pb(b);
		v[b].pb(a);
	}

	dfs(1,1);
	int ans=0;
	vector <pii> vec;
	for(int i=1;i<=n;i++){
		if (deg[i] == 1) ++ans,vec.pb({tin[i],i});
	} 

	sort(vec.begin(),vec.end());
	cout<<(ans + 1)/2<<endl;
	int mid = vec.size()/2;
	if (ans&1) mid++;

	for (int i=0;i<vec.size()/2;i++){
		cout<<vec[i].s<<" "<<vec[mid++].s<<endl;
	}

	if (ans&1){
		cout<<vec[vec.size()/2].s<<" "<<vec[0].s<<endl;
	}

}

Compilation message (stderr)

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

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