Submission #1122052

#	Time	Username	Problem	Language	Result	Execution time	Memory
1122052		Pwo	Network (BOI15_net)	C++17	100 / 100	586 ms	76976 KiB

net

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

int n, leaves[500005], tot = 0;
bool visited[500005];
vector<int> g[500005];
vector<int> st[500005];
vector<int> ans;

void dfs(int v, int p) {
	if (g[v].size() == 1) {
		leaves[v] = 1;
	}
    for (const int u : g[v]) {
        if (u != p) {
			dfs(u, v);
			leaves[v] += leaves[u];
		}
    }
}

int centroid(int v, int p) {
	for (const int u : g[v]) {
		if (u != p) {
			if (leaves[u] * 2 > tot)
				return centroid(u, v);
		}
	}
	return v;
}

void dfs2(int v, int p, int i) {
	if (g[v].size() == 1) {
		st[i].push_back(v);
	}
    for (const int u : g[v]) {
        if (u != p) {
			dfs2(u, v, i);
		}
    }
} 

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);
    }
    
    for (int i = 1; i <= n; i++) if (g[i].size() == 1) tot++;
	
	dfs(1, 1);
	int cent = centroid(1, 1);
	for (int i = 0; i < g[cent].size(); i++) {
		dfs2(g[cent][i], cent, i);
	}
		
	int cnt = (tot + 1) / 2;
	ans.resize(cnt * 2);
	int idx = 0;
	for (int i = 0; i < g[cent].size(); i++) {
		for (const int u : st[i]) {
			ans[idx] = u;
			idx += 2;
			if (idx >= cnt * 2) idx = 1;
		} 
	}
	
	if (ans.back() == 0) ans.back() = st[0][0];
	
	cout << cnt << '\n';
	for (int i = 0; i < ans.size(); i += 2) {
		cout << ans[i] << ' ' << ans[i + 1] << '\n';
	}
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
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 < g[cent].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
net.cpp:63: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]
   63 |  for (int i = 0; i < g[cent].size(); i++) {
      |                  ~~^~~~~~~~~~~~~~~~
net.cpp:74: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]
   74 |  for (int i = 0; i < ans.size(); i += 2) {
      |                  ~~^~~~~~~~~~~~

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