Submission #629969

#	Time	Username	Problem	Language	Result	Execution time	Memory
629969		MinaRagy06	Network (BOI15_net)	C++17	0 / 100	1 ms	212 KiB

net

#include <bits/stdc++.h>
using namespace std;
#define lesgooo ios_base::sync_with_stdio(0), cin.tie(0), cout.tie(0)
#define endl    '\n'
#define int     long long

vector<vector<int>> adj;
int pos, mx = -1e18;
void dfs2(int i, int sum, int par)
{
    if (sum >= mx) mx = sum ,pos = i;
    for (auto nxt : adj[i]) if (nxt != par) dfs2(nxt, sum+1, i);
}
vector<pair<int, int>> dfs(int i, int par)
{
    if (adj[i].size() ==1) return {{0ll, i}};
    vector<pair<int, int>> ret;
    for (auto nxt : adj[i]) if (nxt != par)
    {
        vector<pair<int,int>> x = dfs(nxt ,i);
        for (auto &j : x) j.first++;
        ret.insert(ret.end(), x.begin(), x.end());
    }
    return ret;
}
signed main()
{
    lesgooo;
    int n, u, v;
    cin >> n;
    adj.resize(n);
    for (int i = 0; i < n-1; i++) cin >> u >> v, adj[--u].push_back(--v), adj[v].push_back(u);
    int idx = 0; mx = 0;
    for (int i = 0; i < n; i++) if ((int)adj[i].size() > mx) idx = i, mx = adj[i].size();
    vector<vector<pair<int,int>>> a;
    for (auto nxt : adj[idx]) a.push_back(dfs(nxt, idx));
    for (int i = 0; i < (int)a.size(); i++) sort(a[i].begin(), a[i].end());
    vector<vector<int>> ans;
    while (1)
    {
        set<vector<int>> s;
        for (int i = 0; i < (int)a.size(); i++) if ((int)a[i].size()) s.insert({-a[i].back().first, a[i].back().second, i});
        if ((int)s.size() <= 1)
        {
            if (s.size() == 1) {dfs2((*s.begin())[1], 0, -1), ans.push_back({(*s.begin())[1]+1, pos+1});}
            break;
        }
        vector<int> x = *s.begin(), y;
        s.erase(s.begin());
        y = *s.begin();
        a[x[2]].pop_back(), a[y[2]].pop_back();
        ans.push_back({x[1]+1, y[1]+1});
    }
    cout << ans.size() << endl;
    for (auto i : ans) cout << i[0] << " " << i[1] << endl;
    return 0;
}

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