Submission #151842

#	Time	Username	Problem	Language	Result	Execution time	Memory
151842		balbit	Network (BOI15_net)	C++14	100 / 100	649 ms	50172 KiB

net

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast", "unroll-loops")
#define ll long long 
#define pii pair<int, int>
#define ull unsigned ll
#define f first
#define s second
#define FOR(i,a,b) for (int i=(a); i<(b); i++)
#define REP(i,n) for (int i=0; i<(n); i++)
#define RREP(i,n) for (int i=(n-1); i>=0; i--)
#define ALL(x) x.begin(),x.end()
#define SZ(x) (int)x.size()
#define SQ(x) (x)*(x)
#define MNTO(a,b) a = min(a,(__typeof__(a))(b))
#define MXTO(a,b) a = max(a,(__typeof__(a))(b))
#define pb push_back
#define SORT_UNIQUE(c) (sort(c.begin(),c.end()), c.resize(distance(c.begin(),unique(c.begin(),c.end()))))
#define debug(x) cerr<<#x<<" is "<<x<<endl
using namespace std;

#define int ll
#define LOCAL 1

const int iinf = 1<<29;
const ll inf = 1ll<<60;
const ll mod = 1e9+7;


void GG(){cout<<"No\n"; exit(0);}

ll mpow(ll a, ll n){ // a^n % mod
    ll re=1;
    while (n>0){
        if (n&1) re = re*a %mod;
        a = a*a %mod;
        n>>=1;
    }
    return re;
}

ll inv (ll b){
    if (b==1) return b;
    return (mod-mod/b) * inv(mod%b) % mod;
}

const int maxn = 5e5+5;
vector<vector<int> > g(maxn);
int indeg [maxn];
vector<int> lf;
bool seen[maxn];

void dfs(int v){
    seen[v] = 1;
    if (indeg[v]==1) lf.pb(1+v);
    for (int u : g[v]){
        if (!seen[u]){
            dfs(u);
        }
    }
}

// #ifdef LOCAL
signed main(){
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int n; cin>>n;
    
    REP(i,n-1){
        int a, b; cin>>a>>b;
        a--; b--; g[a].pb(b); g[b].pb(a); 
        indeg[a]++; indeg[b]++;
    }

    dfs(0);
    int hf = (SZ(lf)+1)/2;
    cout<<(SZ(lf)+1)/2<<'\n';
    REP(i,SZ(lf)/2){
        cout<<lf[i]<<' '<<lf[i+hf]<<'\n';
    }
    if (SZ(lf) &1){
        cout<<lf[(SZ(lf))/2]<<' '<<lf[0]<<'\n';
    }
}
// #endif

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