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
#include "kollib.h"
#include "message.h"

#include <iostream>
#include <cstdio>
#include <vector>

using namespace std;

int main() {
  if (MyNodeId() == 0) {
    int qps = (NumberOfQueries()/(NumberOfNodes()-1));
    int targetNode = 1;
    int targetNodeElems = qps;
    for (int i = 1; i <= NumberOfQueries(); ++i) {
      if (targetNodeElems <= 0) {
        targetNodeElems = qps;
        targetNode++;
        if (targetNode >= NumberOfNodes())
          targetNode = NumberOfNodes()-1;
      }
      //cout << " " << QueryFrom(i) << ":"<<QueryTo(i) << " do wezla " << targetNode << endl;
      PutInt(targetNode, QueryFrom(i));
      PutInt(targetNode, QueryTo(i));
      targetNodeElems--;
    }

    for (int i = 1; i < NumberOfNodes(); ++i) {
      PutInt(i, -1);
      Send(i);
    }

    for (int i = 1; i < NumberOfNodes(); ++i) {
      Receive(i);
      while (true) {
        int e = GetInt(i);
        if (e == -1)
          break;
        printf("%d\n", e);
      }
    }

  } else {
    Receive(0);
    vector<pair<int,int> > queries;
    while (true) {
      int e1 = GetInt(0);
      if (e1 == -1) break;
      int e2 = GetInt(0);
      queries.push_back(make_pair(e1, e2));
    }

    for (int i = 0; i < queries.size(); ++i) {
      if (queries[i].first == queries[i].second) {
        PutInt(0,0);
        continue;
      }
      int leftNeighbor = FirstNeighbor(queries[i].first);
      int rightNeighbor = SecondNeighbor(queries[i].first);
      int leftPrevious = queries[i].first, rightPrevious = queries[i].first;
      int target = queries[i].second;
      int ldis = 1, rdis = 1;

      while (true) {
        if (leftNeighbor == target || rightNeighbor == target)
          break;

        //cout << "ln: " << leftNeighbor << " rn: " << rightNeighbor << " prevl: " << leftPrevious << " prevr: " << rightPrevious << endl;

        if (leftPrevious == FirstNeighbor(leftNeighbor)) {
          int tmp = leftNeighbor;
          leftNeighbor = SecondNeighbor(leftNeighbor);

          leftPrevious = tmp;
        } else {
          int tmp = leftNeighbor;

          leftNeighbor = FirstNeighbor(leftNeighbor);

          leftPrevious = tmp;
        }

        if (rightPrevious == FirstNeighbor(rightNeighbor)) {
          int tmp = rightNeighbor;

          rightNeighbor = SecondNeighbor(rightNeighbor);

          rightPrevious = tmp;
        } else {
          int tmp = rightNeighbor;

          rightNeighbor = FirstNeighbor(rightNeighbor);

          rightPrevious = tmp;
        }

        ldis++;
        rdis++;
      }
      PutInt(0, min(ldis, rdis));
    }

    PutInt(0, -1);
    Send(0);
  }

  return 0;
}