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
#include "kollib.h"
#include "message.h"
#include <algorithm>
#include <cstdio>
#include <iostream>
#include <map>
using namespace std;
map <int, int> maps, ms;
int n;
#define ZERO 1000000009
int brut_limit = //200000000;
0;
int licz;
bool brutuj = false;
int limit;
//int MyNodeId(){return 0;}
/*void lec(int pos, int par, int ileJeszcze){
    if(ileJeszcze == limit)return;
   // printf("jestem w %d, numer %d\n", pos, ileJeszcze);
    int a, b;

    a = FirstNeighbor(pos);
    b = SecondNeighbor(pos);
    if(maps.count(pos) != 0){
            maps[pos] = ileJeszcze;
    }
    if(a != par)lec(a, pos, ileJeszcze + 1);
    else lec(b, pos, ileJeszcze + 1);
}*/
void lec(int pos, int par, int ileJeszcze){
    int a, b;
    for(int i=ileJeszcze; i<=limit; i++){
        a = FirstNeighbor(pos);
        b = SecondNeighbor(pos);
        if(maps.count(pos) != 0){
                maps[pos] = i;
        }
        if(a != par){
                par = pos;
                pos = a;
        }
        else{
                par = pos;
                pos = b;
        }
    }
}
int wynikDla(int a){
     if(a < 0)a = -a;
     return min(a, n-a);
}
int main (){
    //cout << "HEEEEEEEE" << endl;
    //if(MyNodeId() == 0)printf("ELO");
    n = NumberOfStudents();
    int m = NumberOfQueries();
    if(n <= brut_limit){
        limit = n;
        brutuj = true;
    } else limit = n/2 + 1;
    for(int i=1; i<=m; i++){
        maps[QueryFrom(i)] = ZERO;
        maps[QueryTo(i)] = ZERO;
    }

    int node = MyNodeId();
    srand(1234);
    int num = rand() % n + 1;
    if(node == 0 || brutuj){
        lec(num, SecondNeighbor(num), 0);
    } else if(node == 1){
        lec(num, FirstNeighbor(num), 0);
    }
    if(node == 1 && !brutuj){
        for(int i=1; i<=m; i++){
            PutInt(0, maps[QueryFrom(i)]);
            PutInt(0, maps[QueryTo(i)]);
        }
        Send(0);
    }
    if(node == 0){
        int a, b;
        int odl = 0;
        if(!brutuj)Receive(1);
        for(int i=1; i<=m; i++){
            a = ZERO;
            b = ZERO;
            if(!brutuj){
                    a = GetInt(1);
                    b = GetInt(1);
                if(a != ZERO)a = n - a;
                if(b != ZERO)b = n - b;
            }
            if(a == ZERO)a = maps[QueryFrom(i)];
            if(b == ZERO)b = maps[QueryTo(i)];
           // printf("przerobilem na %d %d\n", a, b);
           if(QueryFrom(i) == QueryTo(i)){
                printf("0\n");
            } else
            printf("%d\n", wynikDla(a - b));
        }
    }
}