Submission #1235868

#	Time	Username	Problem	Language	Result	Execution time	Memory
1235868		chikien2009	Network (BOI15_net)	C++20	100 / 100	197 ms	38768 KiB

net

#include <bits/stdc++.h>

using namespace std;

void setup()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
}

int n, a, b, f[500000];
vector<int> g[500000]; 
deque<int> temp, l, r;

inline void DFS(int node, int par)
{
    f[node] = (g[node].size() == 1);
    for (auto &i : g[node])
    {
        if (i != par)
        {
            DFS(i, node);
            f[node] += f[i];
        }
    }
}

inline int FindCenter(int node, int par)
{
    for (auto &i : g[node])
    {
        if (i != par && f[i] * 2 > f[0])
        {
            return FindCenter(i, node);
        }
    }
    return node;
}

inline void Get(int node, int par, deque<int> & inp)
{
    if (g[node].size() == 1)
    {
        inp.push_back(node + 1);
    }
    for (auto & i : g[node])
    {
        if (i != par)
        {
            Get(i, node, inp);
        }
    }
}

int main()
{
    setup();

    cin >> n;
    for (int i = 0; i < n - 1; ++i)
    {
        cin >> a >> b;
        g[a - 1].push_back(b - 1);
        g[b - 1].push_back(a - 1);
    }
    DFS(0, 0);
    a = FindCenter(0, 0);
    for (auto & i : g[a])
    {
        temp.clear();
        Get(i, a, temp);
        if (l.size() < r.size())
        {
            for (auto & i : temp)
            {
                l.push_back(i);
            }
        }
        else
        {
            for (auto & i : temp)
            {
                r.push_back(i);
            }
        }
    }
    cout << (f[0] + 1) / 2 << "\n";
    if (l.size() < r.size())
    {
        swap(l, r);
    }
    while (l.size() > r.size() + 1)
    {
        cout << l.front() << " " << l.back() << "\n";
        l.pop_back();
        l.pop_front();
    }
    while (!r.empty())
    {
        cout << l.back() << " " << r.back() << "\n";
        l.pop_back();
        r.pop_back();
    }
    if (!l.empty())
    {
        cout << a + 1 << " " << l.back();
    }
    return 0;
}

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