Submission #1301997

#	Time	Username	Problem	Language	Result	Execution time	Memory
1301997		PakinDioxide	Network (BOI15_net)	C++17	18 / 100	4 ms	14652 KiB

net

#include <bits/stdc++.h>
#define ll long long

using namespace std;

int main() {
    ios::sync_with_stdio(0), cin.tie(0);
    int n; cin >> n;
    vector <int> adj[n+1];
    for (int i = 1, u, v; i < n; i++) cin >> u >> v, adj[u].emplace_back(v), adj[v].emplace_back(u);
    auto bfs = [&] (int st) {
        queue <int> q;
        int vis[n+1]; memset(vis, 0, sizeof(vis));
        int rc = -1;
        q.emplace(st);
        while (!q.empty()) {
            int u = q.front(); q.pop();
            rc = u;
            vis[u] = 1;
            for (auto v : adj[u]) if (!vis[v]) q.emplace(v), vis[v] = 1;
        }
        return rc;
    };
    int D1 = bfs(1);
    int D2 = bfs(D1);
    int dia[n+1]; memset(dia, 0, sizeof(dia));
    function <int(int, int)> fd = [&] (int u, int p) {
        dia[u] = (u == D1 || u == D2);
        for (auto v : adj[u]) if (v != p) dia[u] = max(dia[u], fd(v, u));
        return dia[u];
    };
    fd(D1, D1);
    vector <vector <int>> V;
    function <void(int, int, vector <int> &)> dfs = [&] (int u, int p, vector <int> &k) {
        int cnt = 0;
        for (auto v : adj[u]) if (v != p && !dia[v]) dfs(v, u, k), cnt++;
        if (cnt == 0 && !dia[u]) k.emplace_back(u);
    };
    for (int i = 1; i <= n; i++) if (dia[i]) {
        vector <int> k;
        dfs(i, i, k);
        if (k.size()) V.emplace_back(k);
        cerr << i << " : ";
        for (auto &e : k) cerr << e << ' '; cerr << '\n';
    }
    vector <pair <int, int>> ans;
    int ss = 0, sz = V.size();
    for (auto &e : V) {
        if (e.size() >= 2) {
            int u = e.back(); e.pop_back();
            int v = e.back(); e.pop_back();
            ss = 1;
            ans.emplace_back(u, D1);
            ans.emplace_back(v, D2);
            if (e.empty()) e.swap(V[--sz]);
            break;
        }
    }
    while (sz > 1) {
        ans.emplace_back(V[0].back(), V[1].back());
        V[0].pop_back();
        V[1].pop_back();
        if (V[1].empty()) V[1].swap(V[--sz]);
        if (V[0].empty()) V[0].swap(V[--sz]);
    }
    while (sz > 0 && !V[0].empty()) ans.emplace_back(V[0].back(), D1), V[0].pop_back();
    if (!ss) ans.emplace_back(D1, D2);
    cout << ans.size() << '\n';
    for (auto &[x, y] : ans) cout << x << ' ' << y << '\n';
}

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