Submission #1354911

#	Time	Username	Problem	Language	Result	Execution time	Memory
1354911		anhdannp12345	Network (BOI15_net)	C++20	100 / 100	221 ms	66232 KiB

net

#include <bits/stdc++.h>
#define ll long long
#define pii pair<int, int>

using namespace std;
const long long N = 500005, N2 = 1e7 + 36, CONST = 9999991, MOD = 1e9 + 7;
int n, ans = 0, child[N], total = 0, cnt = 0, a[N], dag[N], counter = 0;
vector<int> adj[N], node[N];
void count_leaves(int x, int par)
{
    child[x] += (adj[x].size() == 1);
    for (int i : adj[x])
    {
        if (i != par)
        {
            count_leaves(i, x);
            child[x] += child[i];
        }
    }
}

int find_centroid(int u, int p)
{
    for (int v : adj[u])
    {
        if (v == p)
            continue;
        if (child[v] > total / 2)
            return find_centroid(v, u);
    }
    if (p != 0 && total - child[u] > total / 2)
        return find_centroid(p, u);
    return u;
}
void get_add(int x, int par)
{
    if (adj[x].size() == 1)
    {
        node[cnt].push_back(x);
        return;
    }
    for (int i : adj[x])
    {
        if (i != par)
        {
            get_add(i, x);
        }
    }
}
int32_t main()
{
    if (fopen("HARU", "r"))
    {
        freopen("Haru", "r", stdin);
        freopen("Fuyu", "w", stdout);
    }
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n;
    for (int i = 1; i < n; ++i)
    {
        int x, y;
        cin >> x >> y;
        adj[x].push_back(y);
        adj[y].push_back(x);
        dag[x]++;
        dag[y]++;
    }
    int root = 1;
    for (int i = 1; i <= n; i++)
    {
        if (dag[i] > 1)
        {
            root = i;
            break;
        }
    }
    count_leaves(root, 0);
    total = child[root];
    int middle = find_centroid(root, 0);
    // for (int i = 1; i < n; ++i)
    //{
    //     cout << child[i] << ' ';
    // }
    // cout << "\n";
    // cout << middle << " " << total << "\n";
    for (int i : adj[middle])
    {
        ++cnt;
        get_add(i, middle);
    }
    for (int i = 1; i <= cnt; ++i)
    {
        for (int j : node[i])
        {
            a[++counter] = j;
        }
    }
    cout << (counter - 1) / 2 + 1 << "\n";
    int pos = a[1];
    for (int i = 1; i <= counter / 2; ++i)
    {
        cout << a[i] << " " << a[i + counter / 2] << "\n";
    }
    if (counter & 1)
    {
        cout << a[counter] << " " << a[1] << "\n";
    }
}

Compilation message (stderr)

net.cpp: In function 'int32_t main()':
net.cpp:54:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   54 |         freopen("Haru", "r", stdin);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~
net.cpp:55:16: warning: ignoring return value of 'FILE* freopen(const char*, const char*, FILE*)' declared with attribute 'warn_unused_result' [-Wunused-result]
   55 |         freopen("Fuyu", "w", stdout);
      |         ~~~~~~~^~~~~~~~~~~~~~~~~~~~~

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