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
/*
 *  Copyright (C) 2014  Paweł Widera
 *
 *  This program is free software; you can redistribute it and/or modify
 *  it under the terms of the GNU General Public License as published by
 *  the Free Software Foundation; either version 3 of the License, or
 *  (at your option) any later version.
 *
 *  This program is distributed in the hope that it will be useful,
 *  but WITHOUT ANY WARRANTY; without even the implied warranty of
 *  MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 *  GNU General Public License for more details:
 *  http://www.gnu.org/licenses/gpl.html
 */

#include "kollib.h"
#include "message.h"

#include <vector>
#include <cmath>
#include <iostream>
using namespace std;


// find the message propagation time
int find(int from, int to) {
	int first = FirstNeighbor(from);
	int first_previous = from;
	int second = SecondNeighbor(from);
	int second_previous = from;
	int time = 1;

	if (from == to) {
		return 0;
	}

	while (first != to && second != to) {
		// move to the first neighbour
		if (FirstNeighbor(first) == first_previous) {
			first_previous = first;
			first = SecondNeighbor(first);
		} else {
			first_previous = first;
			first = FirstNeighbor(first);
		}

		// move to the second neighbour
		if (FirstNeighbor(second) == second_previous) {
			second_previous = second;
			second = SecondNeighbor(second);
		} else {
			second_previous = second;
			second = FirstNeighbor(second);
		}

		++time;
	}
	return time;
}


int main() {
	int n = NumberOfQueries();
	int k = NumberOfNodes();

	int range = ceil(n / float(k));
	int start = MyNodeId() * range + 1;
	int end = min((MyNodeId() + 1) * range + 1, n + 1);

	if (MyNodeId() > 0) {
		PutInt(0, start);
		PutInt(0, end);
		for (int i = start; i < end; ++i) {
			PutInt(0, find(QueryFrom(i), QueryTo(i)));
		}
		Send(0);
	}

	if (MyNodeId() == 0) {
		vector<int> times(n);

		for (int i = start; i < end; ++i) {
			times[i - 1] = find(QueryFrom(i), QueryTo(i));
		}

		for (int i = 1; i < k; ++i) {
			int node = Receive(-1);
			start = GetInt(node);
			end = GetInt(node);
			for (int j = start; j < end; ++j) {
				times[j - 1] = GetInt(node);
			}
		}

		ios::sync_with_stdio (false);

		for (auto time : times) {
			cout << time << endl;
		}
	}
	return 0;
}