Submission #394707

#	Time	Username	Problem	Language	Result	Execution time	Memory
394707		Parsa_PG	Network (BOI15_net)	C++14	100 / 100	693 ms	65360 KiB

net

/* Man BINAHAYATO Mikham */
#include <bits/stdc++.h>
     
#define pb push_back
#define endl "\n"
#define ll long long
 
using namespace std;
 
const int maxn = 1e6 + 10, Maxn = 1e5 + 10, SQ = 360 , lg = 22 ; 
const int mod = 1e9 + 7;
const long long inf = 1e18 + 10;

int sum[maxn], maxx[maxn], cnt, root;
vector<int> adj[maxn], vec;

void find_root(int v, int par){
        for(auto u: adj[v]){
                if(u == par)
                        continue;
                find_root(u, v);
                sum[v] += sum[u];
                maxx[v] = max(maxx[v], sum[u]);
        }
        maxx[v] = max(maxx[v], cnt - sum[v]);
        if(maxx[v] <= cnt/2)
                root = v;
}

void dfs(int v, int par){
        if(adj[v].size() == 1)
                vec.pb(v);
        for(auto u : adj[v])
                if(par != u)
                        dfs(u, v);
}

int32_t main(){
        ios:: sync_with_stdio(0), cin.tie(0), cout.tie(0);
        int n;
        cin >> n;
        for(int i = 0 ; i < n - 1 ; i++){
                int u, v;
                cin >> u >> v;
                u--, v--;
                adj[u].pb(v);
                adj[v].pb(u);
        }
        for(int i = 0 ; i < n ; i++)
                if(adj[i].size() == 1)
                        cnt++;
        find_root(0, -1);
        dfs(root, -1);
        int x = cnt/2;
        cout << (cnt + 1)/2 << endl;
        for(int i = 0 ; i < (cnt + 1)/2 ; i++){
                cout << vec[i] + 1 << ' ' << vec[min(cnt - 1, i + x)] + 1 << endl;
        }
        return 0;
}

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