Submission #1121481

#	Time	Username	Problem	Language	Result	Execution time	Memory
1121481		Pwo	Network (BOI15_net)	C++17	0 / 100	9 ms	12192 KiB

net

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

int n, depth[500005], par[500005];
vector<int> g[500005];
vector<int> leaves;

void dfs(int v, int p, bool b) {
    depth[v] = depth[p] + 1;
    par[v] = p;
    int cnt = 0;
    for (const int u : g[v]) {
        if (u != p) cnt++, dfs(u, v, b);
    }
    if (b && cnt == 0) leaves.push_back(v);
}

int32_t main() {
    cin >> n;
    for (int i = 1; i < n; i++) {
        int u, v; cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);
    }

    dfs(1, 1, 0);
    int mx = 0, node = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] > mx) mx = depth[i], node = i;
    }

    fill(depth, depth + n + 1, 0);
    dfs(node, node, 1);
    mx = 0; int node2 = 0;
    for (int i = 1; i <= n; i++) {
        if (depth[i] > mx) mx = depth[i], node2 = i;
    }
    
    if (leaves.size() == 1) {
		cout << 1 << '\n';
		cout << node << ' ' << node2;
	} else if (leaves.size() == 2) {
		cout << 2 << '\n';
		cout << leaves[0] << ' ' << leaves[1] << '\n';
		cout << leaves[1] << ' ' << node;
	} else {
		cout << leaves.size() - 1 << '\n';
		cout << node << ' ' << leaves[1] << '\n';
		cout << node2 << ' ' << leaves[2] << '\n';
		for (int i = 3; i < leaves.size(); i++)
			cout << leaves[i] << ' ' << leaves[i - 1] << '\n';
	}
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:51:21: 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]
   51 |   for (int i = 3; i < leaves.size(); i++)
      |                   ~~^~~~~~~~~~~~~~~

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