Submission #997025

#	Time	Username	Problem	Language	Result	Execution time	Memory
997025		underwaterkillerwhale	Network (BOI15_net)	C++17	100 / 100	317 ms	118856 KiB

net

#include <bits/stdc++.h>
#define se              second
#define fs              first
#define mp              make_pair
#define pb              push_back
#define ll              long long
#define ii              pair<ll,ll>
#define ld              long double
#define SZ(v)           (int)v.size()
#define ALL(v)          v.begin(), v.end()
#define bit(msk, i)     ((msk >> i) & 1)
#define iter(id, v)     for(auto id : v)
#define rep(i,m,n)      for(int i=(m); i<=(n); i++)
#define reb(i,m,n)      for(int i=(m); i>=(n); i--)

using namespace std;

mt19937_64 rd(chrono :: steady_clock :: now().time_since_epoch().count());
ll Rand(ll l, ll r) { return uniform_int_distribution<ll> (l, r)(rd); }

const int N  = 5e5 + 7;
const int Mod = 998244353;
const int szBL = 916;
const ll INF = 1e18;
const int BASE = 137;

int n;
vector<int> ke[N];

int in[N], out[N];

vector<pair<int,int>> Ans;

vector<int> dfs (int u, int p) {
    if (SZ(ke[u]) == 1) return vector<int> (1, u);
    vector<int> prv;
    iter (&v, ke[u]) {
        if (v == p) continue;
        vector<int> cur = dfs (v, u);
        if (SZ(cur) > SZ(prv)) swap(cur, prv);
        while (SZ(prv) + SZ(cur) > 2 && cur.size()) {
            Ans.push_back(mp(cur.back(), prv.back()));
            cur.pop_back();
            prv.pop_back();
        }
        iter (&id, cur) prv.push_back(id);
    }
    return prv;
}

void solution () {
    cin >> n;
    rep (i, 1, n - 1) {
        int u, v;
        cin >> u >> v;
        ke[u].push_back(v);
        ke[v].push_back(u);
    }
    int root = 1;
    rep (i, 1, n) if (SZ(ke[i]) > 1) root = i;
    vector<int> cur = dfs (root, 0);
    if (SZ(cur) == 1) cur.push_back(root);
    Ans.push_back(mp(cur[0], cur[1]));
    cout << SZ(Ans) <<"\n";
    iter (&id, Ans) cout << id.fs<< " "<<id.se <<"\n";


}
#define file(name) freopen(name".inp", "r", stdin); freopen(name".out", "w", stdout);
int main () {
    ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);

//    file ("fbuy");
    int num_Test = 1;
//    cin >> num_Test;
    while (num_Test--)
        solution();
}
/*
7
1 2 4
2 3 12
3 4 2
4 5 48
5 6 2
6 7 123

*/

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