Submission #1173928

#	Time	Username	Problem	Language	Result	Execution time	Memory
1173928		LucaIlie	Network (BOI15_net)	C++20	100 / 100	336 ms	45476 KiB

net

#include <bits/stdc++.h>

using namespace std;

const int MAX_N = 5e5;
vector<int> adj[MAX_N + 1];

vector<int> order;

void dfs( int u, int p ) {
    if ( adj[u].size() == 1 )
        order.push_back( u );
    for ( int v: adj[u] ) {
        if ( v == p )
            continue;
        dfs( v, u );
    }
}

int main() {
    cin.tie( nullptr );
    ios_base::sync_with_stdio( false );

    int n;

    cin >> n;
    for ( int i = 0; i < n - 1; i++ ) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back( v );
        adj[v].push_back( u );
    }

    int r = 1;
    while ( adj[r].size() == 1 )
        r++;

    dfs( r, 0 );

    int k = (order.size() + 1) / 2;
    cout << k << "\n";
    for ( int i = 0; i < k; i++ )
        cout << order[i] << " " << order[min( (int)order.size() - 1, i + k )] << "\n";

    return 0;
}

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