Submission #623007

#	Time	Username	Problem	Language	Result	Execution time	Memory
623007		MinaRagy06	Network (BOI15_net)	C++17	18 / 100	103 ms	31976 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<int> adj[2006];
int dist[2006][2006];
void dfs(int i, int sum, int src, int par)
{
    dist[src][i] = sum;
    for (auto nxt : adj[i]) if (nxt != par) dfs(nxt, sum+1, src, i);
}
signed main()
{
    lesgooo;
    int n, u, v;
    cin >> n;
    mt19937 rng(2006);
    for (int i = 1; i < n; i++) cin >> u >> v, adj[--u].push_back(--v), adj[v].push_back(u);
    set<int> leaf;
    for (int i = 0;i < n; i++)
    {
        dfs(i, 0, i, -1);
        if (adj[i].size() == 1) leaf.insert(i);
    }
    cout << (leaf.size()+1)/2 << endl;
    int temp = *leaf.begin();
    while (leaf.size() > 1)
    {
        int cur = *leaf.begin(), mx = -1;
        vector<int> aa;
        for (int i = 0; i < n; i++) if (i != cur && leaf.find(i) != leaf.end())
        {
            if (dist[cur][i] > mx) mx = dist[cur][i], aa.clear(), aa.push_back(i);
            else if (dist[cur][i] == mx) aa.push_back(i);
        }
        int x= aa.back();
        cout << cur+1 << " " << x+1 << endl;
        leaf.erase(leaf.begin()), leaf.erase(x);
    }
    if (leaf.size()) cout << *leaf.begin()+1 << " " << (*leaf.begin()+1)%n+1 << endl, leaf.erase(leaf.begin());
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:28:9: warning: unused variable 'temp' [-Wunused-variable]
   28 |     int temp = *leaf.begin();
      |         ^~~~

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