Submission #414033

#	Time	Username	Problem	Language	Result	Execution time	Memory
414033		Rudy420	Network (BOI15_net)	C++17	100 / 100	616 ms	100712 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define x first
#define y second
#define lg length()
#define pb push_back
#define INF 2000000005
#define LINF 1000000000000000005
#define all(x) (x).begin(), (x).end()
#define rep(i, a, b) for(int i = a; i < (b); ++i)
#define sz(x) (int)(x).size()
typedef long long ll;
typedef pair<int, int> pii;
typedef pair<ll, ll> pll;
typedef vector<int> vi;
mt19937 rng(chrono::steady_clock::now().time_since_epoch().count());
int rand(int l,int r){return uniform_int_distribution<int>(l,r)(rng);}
#define int ll

int n,x,y,dp[500005][2],u[500005],v[500005];

vector <pii> ans;

vector <int> g[500005];

void DFS(int nod, int par){
    int sum = 0, p = 0;
    int A = 0, B = 0;
    for(int i : g[nod]){
        if(i == par) continue;
        DFS(i, nod);
        if(dp[i][1] <= dp[i][0]){
            sum += dp[i][1];
            p++;
            if(B) ans.pb({B, u[i]}), B = 0;
            else if(A) B = u[i];
            else A = u[i];

        }
        else{
            sum += dp[i][0];
            p+=2;
            if(B) ans.pb({B, u[i]}), B = v[i];
            else if(A) ans.pb({A, u[i]}), A = v[i];
            else A = u[i], B = v[i];
        }
    }
    dp[nod][1] = sum + p / 2;
    dp[nod][0] = sum + (p - 1) / 2;
    if(par == -1){
        if(B) ans.pb({A,B});
        else if(A) ans.pb({A,nod});
    }
    else if(dp[nod][1] <= dp[nod][0]){
        if(B) ans.pb({B, nod});
        if(!A) A = nod;
        u[nod] = A;
    }
    else{
        if(!A) A = nod;
        if(!B) B = nod;
        u[nod] = A, v[nod] = B;
    }
}

int32_t main(){
    ios_base :: sync_with_stdio(0); cin.tie(); cout.tie();
#ifdef LOCAL_DEFINE
    ifstream cin("input.txt");
#endif

    cin >> n;
    for(int i=1;i<n;i++){
        cin >> x >> y;
        g[x].pb(y);
        g[y].pb(x);
    }

    int root = -1;
    for(int i=1;i<=n;i++){
        if(sz(g[i]) > 1) root = i;
    }

    DFS(root,-1);

    cout << sz(ans) << '\n';
    for(pii i : ans) cout << i.x << ' ' << i.y << '\n';

}

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