Submission #1034514

#	Time	Username	Problem	Language	Result	Execution time	Memory
1034514		sinatbtfard	Network (BOI15_net)	C++17	100 / 100	280 ms	47824 KiB

net

#include <bits/stdc++.h>

#define pb push_back

using namespace std;

const int maxn = 5e5 + 1;

int n;
vector <int> leaves, adj[maxn];
 
void dfs (int v, int p){
    if (adj[v].size() == 1)
        leaves.pb(v);
    for (auto u : adj[v])
        if (u != p)
            dfs(u, v);
}

int main(){
	ios_base::sync_with_stdio(0);
	cin >> n;
	for (int x, y, i = 1; i < n; i++){
		cin >> x >> y;
		adj[x].pb(y);
		adj[y].pb(x);
	}
	for (int i = 1; i <= n; i++){
	    if (adj[i].size() != 1){
	        dfs(i, -1);
	        break;
	    }
	}
	cout << (leaves.size() + 1) / 2 << '\n';
	for(int i = 0; i < (leaves.size() + 1) / 2; i++) 
		cout << leaves[i] << " " << leaves[i + (leaves.size() / 2)] << '\n';
}

Compilation message (stderr)

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

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