1
  2
  3
  4
  5
  6
  7
  8
  9
 10
 11
 12
 13
 14
 15
 16
 17
 18
 19
 20
 21
 22
 23
 24
 25
 26
 27
 28
 29
 30
 31
 32
 33
 34
 35
 36
 37
 38
 39
 40
 41
 42
 43
 44
 45
 46
 47
 48
 49
 50
 51
 52
 53
 54
 55
 56
 57
 58
 59
 60
 61
 62
 63
 64
 65
 66
 67
 68
 69
 70
 71
 72
 73
 74
 75
 76
 77
 78
 79
 80
 81
 82
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
#include "kollib.h"
#include "message.h"
#include <iostream>
#include <cstdlib>
#include <unordered_set>
#include <unordered_map>
#include <vector>
#include <utility>
using namespace std;
typedef pair<int,int> PII;

PII go(int from, int dir, unordered_set<int>& special) {
  // cerr << "go(" << from << ", " << dir << ")" << endl;
  int dist = 1;
  while (special.find(dir) == special.end()) {
    dist++;
    int nei = FirstNeighbor(dir);
    if (nei == from) {
      nei = SecondNeighbor(dir);
    }
    from = dir;
    dir = nei;
  }
  return PII(dir, dist);
}

struct ListStruct {
  int first, firstDistance;
  int second, secondDistance;
  ListStruct(int f=0, int fd=0, int s=0, int sd=0) : first(f), firstDistance(fd), second(s), secondDistance(sd) {}
};

int dist(int from, int to, unordered_map<int, ListStruct>& lst) {
  // cerr << "dist(" << from << ", " << to << ")" << endl;
  int res = 0;
  int prev = lst[from].first;
  while (from != to) {
    ListStruct vl = lst[from];
    int nei = vl.first;
    int d = vl.firstDistance;
    if (prev == nei) {
      nei = vl.second;
      d = vl.secondDistance;
    }
    res += d;
    prev = from;
    from = nei;
  }
  return res;
}

int main() {
  srand(23);
  int N = NumberOfNodes();
  int ID = MyNodeId();

  int n = NumberOfStudents();
  int q = NumberOfQueries();
  unordered_set<int> special;
  vector<int> for_me;

  for (int i = 0; i < q; ++i) {
    int a = QueryFrom(i+1);
    int b = QueryTo(i+1);
    bool add = special.insert(a).second;
    if (add and i % N == ID) {
      for_me.push_back(a);
    }
    add = special.insert(b).second;
    if (add and i % N == ID) {
      for_me.push_back(b);
    }
  }

  int points = max(10 * N, min(5000, n / 100000));
  //int points = 100;
  for (int i = 0; i < points; ++i) {
    int p = 1 + rand() % n;
    bool add = special.insert(p).second;
    if (i % N == ID and add) {
      for_me.push_back(p);
    }
  }

  PutInt(0, for_me.size());
  for (int p : for_me) {
    PutInt(0, p);
    PII first = go(p, FirstNeighbor(p), special);
    PII second = go(p, SecondNeighbor(p), special);
    PutInt(0, first.first);
    PutInt(0, first.second);
    PutInt(0, second.first);
    PutInt(0, second.second);
  }
  Send(0);

  if (ID == 0) {
    unordered_map<int, ListStruct> lst;
    for (int i = 0; i < N; ++i) {
      int inst = Receive(-1);
      int m = GetInt(inst);
      for (int j = 0; j < m; ++j) {
        int p = GetInt(inst);
        int l, ld, r, rd;
        l = GetInt(inst);
        ld = GetInt(inst);
        r = GetInt(inst);
        rd = GetInt(inst);
        lst[p] = ListStruct(l, ld, r, rd);
      }
    }

    for (int i = 0; i < q; ++i) {
      int a = QueryFrom(i+1);
      int b = QueryTo(i+1);
      int d = dist(a, b, lst);
      printf("%d\n", min(d, n-d));
    }
  }
  return 0;
}