Submission #422707

#	Time	Username	Problem	Language	Result	Execution time	Memory
422707		Harry464	Network (BOI15_net)	C++14	100 / 100	1012 ms	93020 KiB

net

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;
typedef long long ll;

vector <vector <ll> > adjl(1000000);
vector <ll> bl(1000000, 0);

ll listovi = 0;

vector <ll> leaf;

void dfs(ll u, ll p){

   for (int i = 0; i < adjl[u].size(); i++){

     ll v = adjl[u][i];
     if (v != p)
        dfs(v,u), bl[u] += bl[v];

   }

   if (adjl[u].size() == 1)
     bl[u] += 1;

}

ll cent(ll u, ll p){

   for (int i = 0; i < adjl[u].size(); i++){

     ll v = adjl[u][i];

     if (v != p){

        if (listovi - bl[v] < bl[v])
            return cent(v, u);

     }

   }

   return u;

}

void relax(ll u, ll p){

   if (adjl[u].size() == 1){

     leaf.push_back(u);
     return;

   }

   for (int i = 0; i < adjl[u].size(); i++){

     ll v = adjl[u][i];
     if (v != p)
        relax(v,u);

   }

}

int main()
{
    ll n;
    cin >> n;

    for (int i = 0; i < n - 1; i++){

        ll u, v;
        cin >> u >> v;
        u--, v--;

        adjl[u].push_back(v), adjl[v].push_back(u);

    }


    ll start = 0;

    for (int i = 0; i < n; i++)
        if (adjl[i].size() != 1)
         start = i;
        else
            listovi++;

    dfs(start, -1);
    ll centroid = cent(start, -1);

    for (int i = 0; i < adjl[centroid].size(); i++){

        ll v = adjl[centroid][i];
        relax(v,centroid);

    }

    cout << (listovi+1)/2 << endl;
    for (int i = 0; i < listovi/2; i++)
        cout << leaf[i] + 1 << " " << leaf[i+listovi/2] + 1 << endl;

    if (listovi%2 == 1)
        cout << leaf[0] + 1 << " " << leaf[listovi-1] + 1<< endl;

}

Compilation message (stderr)

net.cpp: In function 'void dfs(ll, ll)':
net.cpp:17:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   17 |    for (int i = 0; i < adjl[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
net.cpp: In function 'll cent(ll, ll)':
net.cpp:32:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   32 |    for (int i = 0; i < adjl[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
net.cpp: In function 'void relax(ll, ll)':
net.cpp:58:22: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   58 |    for (int i = 0; i < adjl[u].size(); i++){
      |                    ~~^~~~~~~~~~~~~~~~
net.cpp: In function 'int main()':
net.cpp:95:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   95 |     for (int i = 0; i < adjl[centroid].size(); i++){
      |                     ~~^~~~~~~~~~~~~~~~~~~~~~~

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