Submission #394610

#	Time	Username	Problem	Language	Result	Execution time	Memory
394610		Mahdi_Shokoufi	Network (BOI15_net)	C++17	100 / 100	495 ms	58892 KiB

net

//In the name of Allah
#include <bits/stdc++.h>

using namespace std;

const int N = 5e5 + 5;

vector < int > adj[N], lf;

void DFS(int v, int p = 0){
    if (adj[v].size() == 1)
        lf.push_back(v);
    for (int u : adj[v])
        if (u != p)
            DFS(u, v);
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(0); cout.tie(0);
    int n, r = 0;
    cin >> n;
    for (int i = 1; i < n; i ++){
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    for (int i = 1; i <= n; i ++)
        if (adj[i].size() != 1)
            r = i;
    DFS(r);
    cout << (lf.size() + 1) / 2 << '\n';
    for (int i = 0; i < lf.size() / 2; i ++)
        cout << lf[i] << ' ' << lf[i + lf.size() / 2] << '\n';
    if (lf.size() & 1)
        cout << lf[0] << ' ' << lf.back() << '\n';
    return 0;
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:34:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   34 |     for (int i = 0; i < lf.size() / 2; i ++)
      |                     ~~^~~~~~~~~~~~~~~

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