Submission #1130901

#	Time	Username	Problem	Language	Result	Execution time	Memory
1130901		ezdubz	Network (BOI15_net)	C++20	100 / 100	647 ms	49688 KiB

net

#include <iostream> 
#include <vector> 
using namespace std; 
#define maxn 500001
vector<int> adj[maxn], l; 
int leaves = 0, n; 
void dfs(int cur, int par) {
    for (int i : adj[cur]) {
        if (i != par) dfs(i, cur); 
    }
    if (adj[cur].size() == 1) {
        leaves++; 
        l.push_back(cur); 
    }
}
int main() {
    cin >> n; 
    for (int i = 0; i < n - 1; i++) {
        int a, b; 
        cin >> a >> b; 
        adj[a].push_back(b); 
        adj[b].push_back(a); 
    } 
    dfs(1, -1); 
    cout << (leaves + 1) / 2 << endl; 
    for (int i = 0; i < leaves/2; i++) {
        cout << l[i] << " " << l[i + leaves/2 + leaves%2] << endl; 
    }
    if (leaves%2 == 1) cout << 1 << " " << l[leaves/2]; 
} 

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