Submission #943959

#	Time	Username	Problem	Language	Result	Execution time	Memory
943959		Ghulam_Junaid	Network (BOI15_net)	C++17	0 / 100	7 ms	25260 KiB

net

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

const int N = 5e5 + 100;
int n, r, alone, intime[N], tme = 0;
vector<int> g[N], leaves[N];

void dfs(int v, int sec = -1, int p = -1){
    bool leaf = 1;
    intime[v] = tme++;
    for (int u : g[v]){
        if (u == p) continue;
        leaf = 0;
        
        if (sec == -1)
            dfs(u, u, v);
        else
            dfs(u, sec, v);
    }

    if (leaf)
        leaves[sec].push_back(v);
}

int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);

    cin >> n;

    for (int i = 0; i < n - 1; i ++){
        int u, v;
        cin >> u >> v;
        g[u].push_back(v);
        g[v].push_back(u);

        if (g[u].size() > g[r].size())
            r = u;
        if (g[v].size() > g[r].size())
            r = v;
    }

    // cout << "root = " << r << endl;
    dfs(r);

    set<pair<int, int>> st;
    for (int i = 1; i <= n; i ++){
        int sz = leaves[i].size();
        // cout << i << " -- " << leaves[i].size() << endl;
        if (sz)
            st.insert({-sz, i});
    }

    vector<pair<int, int>> ans;
    while (st.size() > 1){
        auto it = st.begin();
        int sz1 = -(*it).first;
        int au = (*it).second;
        it++;
        int sz2 = -(*it).first;
        int av = (*it).second;

        st.erase(st.begin());
        st.erase(st.begin());

        int u = leaves[au].back();
        int v = leaves[av].back();
        leaves[au].pop_back();
        leaves[av].pop_back();

        alone = u;
        ans.push_back({u, v});
        if (sz1 > 1)
            st.insert({-sz1 + 1, au});
        if (sz2 > 1)
            st.insert({-sz2 + 1, av});
    }

    if (st.size()){
        int av = (*st.begin()).second;
        st.clear();
        for (int l : leaves[av])
            st.insert({intime[l], l});
        while (st.size() > 1){
            int u = (*st.begin()).second;
            int v = (*st.rbegin()).second;
            st.erase({intime[u], u});
            st.erase({intime[v], v});

            alone = u;
            ans.push_back({u, v});
        }

        if (st.size()){
            int v = (*st.begin()).second;
            ans.push_back({v, alone});
        }
    }

    cout << ans.size() << endl;
    for (auto [u, v] : ans)
        cout << u << " " << v << endl;
}

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