High Load


Arkady needs your help again! This time he decided to build his own high-speed Internet exchange point. It should consist of $n$ nodes connected with minimum possible number of wires into one network (a wire directly connects two nodes). Exactly $k$ of the nodes should be exit-nodes, that means that each of them should be connected to exactly one other node of the network, while all other nodes should be connected to at least two nodes in order to increase the system stability.
Arkady wants to make the system as fast as possible, so he wants to minimize the maximum distance between two exit-nodes. The distance between two nodes is the number of wires a package needs to go through between those two nodes.
Help Arkady to find such a way to build the network that the distance between the two most distant exit-nodes is as small as possible.


数据范围:$3 \le n \le 2 \times 10^5, \; 2 \le k \le n-1$。






#include <cstdio>
#include <queue>
using namespace std;
struct edge {
  int v, nxt;
} e[400001];
int n, m, nume, h[200001], depth[200001];
queue<int> que;
void add_edge(int u, int v) {
  e[++nume].v = v, e[nume].nxt = h[u], h[u] = nume;
int main()
  scanf("%d%d", &n, &m);;
  for (int i = 1; i <= m; ++i) {
    add_edge(1, i + 1), depth[i + 1] = 1;
    que.push(i + 1);
  for (int i = m + 2; i <= n; ++i) {
    int u = que.front(); que.pop();
    add_edge(u, i), depth[i] = depth[u] + 1;
  printf("%d\n", depth[n] + depth[n - 1]);
  for (int i = 1; i <= n; ++i) {
    for (int j = h[i]; j; j = e[j].nxt) {
      printf("%d %d\n", i, e[j].v);
  return 0;

RegMs If

418 I'm a teapot

Leave a Reply

Your email address will not be published. Required fields are marked *