Submission #394618

#	Time	Username	Problem	Language	Result	Execution time	Memory
394618		suto	Network (BOI15_net)	C++17	100 / 100	539 ms	45768 KiB

net

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
typedef long double ld;
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef pair<double, double> pdd;
typedef pair<ld , ll> pdl;
typedef string str;

#define all(x)                      (x).begin(),(x).end()
#define Sort(x)                     sort(all((x)))
#define X                           first
#define Y                           second
#define Mp                          make_pair
#define pb(x)                       push_back(x)
#define pf(x)                       push_front(x)
#define sep                         ' '
#define endl                        '\n'
#define debug(x)                    cerr << #x << " = " << x << endl
#define SZ(x)                       ll(x.size())
#define fast_io                     ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);

const ll MAXN = 5e5 + 10;
const ll INF = 1e18 + 10;
const ll LOG = 1e7 + 19;
const ll MOD = 998244353;

ll pw(ll a , ll b, ll M)  { return (!b ? 1 : (b & 1 ? (a * pw(a * a % M, b / 2, M)) % M : pw(a * a % M, b / 2, M))); }

ll a[MAXN] , mark[MAXN];
vector <ll> adj[MAXN] , barg;

void dfs(ll v){

    mark[v] = 1;
    if(adj[v].size() == 1){
        barg.pb(v);
        return;
    }
    for(auto u: adj[v]){
        if(!mark[u]){
            dfs(u);
        }
    }

}

int main(){

    fast_io;
    ll n;
    cin >> n;
    for(int i = 1; i < n; i++){
        ll v , u;
        cin >> v >> u;
        adj[v].pb(u);
        adj[u].pb(v);
    }
    ll root = 0;
    for(int i = 1; i <= n; i++){
        if(adj[i].size() > 1){
            root = i;
            break;
        }
    }
    dfs(root);
    ll k = barg.size() , p = (k + 1) / 2;
    k /= 2;
    cout << p << endl;
    for(int i = 0; i < p; i++){
        cout << barg[i] << sep << barg[i + k] << endl;
    }

}

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