제출 #442798

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
442798		palilo	Network (BOI15_net)	C++17	0 / 100	0 ms	204 KiB

net

#include <bits/stdc++.h>
using namespace std;

int main() {
    cin.tie(nullptr)->sync_with_stdio(false);
#ifdef palilo
    freopen("in", "r", stdin);
    freopen("out", "w", stdout);
#endif
    int n;
    cin >> n;
    vector<vector<int>> adj(n);
    for (int u, v, i = n - 1; i--;) {
        cin >> u >> v, --u, --v;
        adj[u].emplace_back(v);
        adj[v].emplace_back(u);
    }
    const auto rev_dfn = [&](int root) {
        vector<int> stk = {root}, dfn(n);
        for (auto& u : dfn) {
            u = stk.back();
            stk.pop_back();
            for (const auto& v : adj[u]) {
                adj[v].erase(find(adj[v].begin(), adj[v].end(), u));
                stk.emplace_back(v);
            }
        }
        reverse(dfn.begin(), dfn.end());
        return dfn;
    }(0);
    vector<pair<int, int>> ans;
    vector dp(n, -1);
    for (const auto& u : rev_dfn) {
        for (const auto& v : adj[u]) {
            if (~dp[v]) {
                if (dp[u] == -1) {
                    dp[u] = dp[v];
                } else {
                    ans.emplace_back(exchange(dp[u], -1), dp[v]);
                }
            }
        }
        if (dp[u] == -1) {
            dp[u] = u;
        }
    }
    if (dp[0]) {
        ans.emplace_back(dp[0], 0);
    }
    cout << ans.size() << '\n';
    for (const auto& [u, v] : ans) {
        cout << u + 1 << ' ' << v + 1 << '\n';
    }
}

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