Submission #53927

#	Time	Username	Problem	Language	Result	Execution time	Memory
53927		ruhanhabib39	Network (BOI15_net)	C++17	100 / 100	840 ms	155956 KiB

net

#include <bits/stdc++.h>
using namespace std;

const int MAXN = 5e5;

int n;
vector<int> G[MAXN + 10];

vector<pair<int,int>> edges;
bool done[MAXN + 10];
int sz[MAXN + 10];

void dfs1(int u, int p = -1) {
   for(int v : G[u]) {
      if(v != p) dfs1(v, u);
   }
   sz[u] = 0;
   if((int)G[u].size() == 1) {
      sz[u] = 1;
   }
   for(int v : G[u]) {
      if(v != p) sz[u] += sz[v];
   }
   return;
}

int lc = 0;
int dfs2(int u, int p = -1) {
   for(int v : G[u]) {
      if(v != p && sz[v] > (lc+1)/2) return dfs2(v, u);
   }
   return u;
}
int centroid(int u) {
   dfs1(u); lc = sz[u];
   return dfs2(u);
}

void work() {
   int root = 1;
   while((int)G[root].size() == 1) ++root;
   root = centroid(root);
   vector<int> leaves;
   for(int v : G[root]) {
      function<void(int,int)> dfs = [&](int u, int p) {
         if((int)G[u].size() == 1) {
            leaves.push_back(u);
         }
         for(int w : G[u]) {
            if(w != p) dfs(w, u);
         }
      };
      dfs(v, root);
   }
   for(int i = 0; i < lc/2; i++) {
      edges.emplace_back(leaves[i], leaves[i + (lc + 1)/2]);
   }
   if(lc & 1) {
      edges.emplace_back(leaves[(lc+1)/2-1], root);
   }
}

int main() {
   scanf("%d", &n);
   for(int i = 1; i < n; i++) {
      int u, v; scanf("%d%d", &u, &v);
      G[u].push_back(v);
      G[v].push_back(u);
   }
   work();
   printf("%d\n", (int)edges.size());
   for(auto it : edges) printf("%d %d\n", it.first, it.second);
}

Compilation message (stderr)

net.cpp: In function 'int main()':
net.cpp:64:9: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
    scanf("%d", &n);
    ~~~~~^~~~~~~~~~
net.cpp:66:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       int u, v; scanf("%d%d", &u, &v);
                 ~~~~~^~~~~~~~~~~~~~~~

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