oj.uz

Submission #943959

# Submission time Handle Problem Language Result Execution time Memory
943959 2024-03-12T05:37:33 Z Ghulam_Junaid Network (BOI15_net) C++17
0 / 100
 7 ms 25260 KB 
#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.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 6 ms 25252 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 5 ms 25260 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 7 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25176 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 5 ms 25180 KB Output is correct
15 Correct 5 ms 25260 KB Output is correct
16 Correct 5 ms 25180 KB Output is correct
17 Correct 5 ms 25180 KB Output is correct
18 Incorrect 5 ms 25180 KB Breaking single line is causing network to disconnect.
19 Halted 0 ms 0 KB -

Subtask #2
0 / 45.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 6 ms 25252 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 5 ms 25260 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 7 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25176 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 5 ms 25180 KB Output is correct
15 Correct 5 ms 25260 KB Output is correct
16 Correct 5 ms 25180 KB Output is correct
17 Correct 5 ms 25180 KB Output is correct
18 Incorrect 5 ms 25180 KB Breaking single line is causing network to disconnect.
19 Halted 0 ms 0 KB -

Subtask #3
0 / 37.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 25180 KB Output is correct
2 Correct 6 ms 25180 KB Output is correct
3 Correct 6 ms 25180 KB Output is correct
4 Correct 6 ms 25252 KB Output is correct
5 Correct 6 ms 25176 KB Output is correct
6 Correct 5 ms 25180 KB Output is correct
7 Correct 5 ms 25260 KB Output is correct
8 Correct 5 ms 25180 KB Output is correct
9 Correct 6 ms 25180 KB Output is correct
10 Correct 7 ms 25180 KB Output is correct
11 Correct 6 ms 25180 KB Output is correct
12 Correct 6 ms 25176 KB Output is correct
13 Correct 6 ms 25180 KB Output is correct
14 Correct 5 ms 25180 KB Output is correct
15 Correct 5 ms 25260 KB Output is correct
16 Correct 5 ms 25180 KB Output is correct
17 Correct 5 ms 25180 KB Output is correct
18 Incorrect 5 ms 25180 KB Breaking single line is causing network to disconnect.
19 Halted 0 ms 0 KB -