Submission #653414

#	Time	Username	Problem	Language	Result	Execution time	Memory
653414		pauloamed	Network (BOI15_net)	C++14	63 / 100	2061 ms	74648 KiB

net

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

const int MAXN = 500010;

struct DSU{
  int sizes[MAXN];
  int parents[MAXN];
  
  DSU(int n){
    for(int i = 0; i < n; ++i){
      sizes[i] = 1;
      parents[i] = i;
    }
  }

  int find(int current){
    int newRoot = current;
    while(newRoot != parents[newRoot]) newRoot = parents[newRoot];

    // rmv if using rollback
    int next;
    while(parents[current] != newRoot){
      next = parents[current];
      parents[current] = newRoot;
    }
    return newRoot;
  }

  void onion(int a, int b){
    a = find(a); b = find(b);
    if(a == b) return;
    if(sizes[a] < sizes[b]) swap(a,b);

    sizes[a] += sizes[b];
    parents[b] = a;
  }
};

vector<int> v[MAXN];
vector<int> u[MAXN];

pair<int,int> deep(int x, int p){
  pair<int,int> ret = {0, x};
  for(auto y : v[x]) if(y != p){
    ret = max(ret, deep(y, x));
  }
  return {ret.first + 1, ret.second};
}

bool mark(int x, int p, int target, DSU &dsu){
  bool has = (x == target);
  for(auto y : v[x]) if(y != p){
    if(mark(y, x, target, dsu)){
      dsu.onion(x, y);
      return true;
    }
  }
  return has;
}

int main(){
  int n; cin >> n;
  for(int i = 0; i + 1 < n; ++i){
    int a, b; cin >> a >> b;
    a--; b--;
    v[a].push_back(b);
    v[b].push_back(a);
  }

  DSU dsu(n);

  vector<pair<int,int>> ans;
  while(dsu.sizes[dsu.find(0)] != n){
    int start = dsu.find(0);
    auto [_, x] = deep(start, -1);
    auto [__, y] = deep(x, -1);

    ans.push_back({x, y});
    mark(x, -1, y, dsu);

    for(int i = 0; i < n; ++i){
      int a = dsu.find(i);
      for(auto y : v[i]){
        int b = dsu.find(y);
        if(a != b){
          u[a].push_back(b);
          u[b].push_back(a);
        }
      }
    }

    for(int i = 0; i < n; ++i) if(dsu.find(i) == i){
      sort(u[i].begin(), u[i].end());
      u[i].erase(unique(u[i].begin(), u[i].end()), u[i].end());
      v[i].clear();
      swap(v[i], u[i]);
    }
  }

  cout << ans.size() << "\n";
  for(auto [a, b] : ans) cout << a + 1 << " " << b + 1 << "\n";

}

Compilation message (stderr)

net.cpp: In member function 'int DSU::find(int)':
net.cpp:22:9: warning: variable 'next' set but not used [-Wunused-but-set-variable]
   22 |     int next;
      |         ^~~~
net.cpp: In function 'int main()':
net.cpp:76:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   76 |     auto [_, x] = deep(start, -1);
      |          ^
net.cpp:77:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
   77 |     auto [__, y] = deep(x, -1);
      |          ^
net.cpp:102:12: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  102 |   for(auto [a, b] : ans) cout << a + 1 << " " << b + 1 << "\n";
      |            ^

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