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

#define st first
#define nd second

const int MAXQ = 205, MAXN = 405;
int queriesNo,queries[2*MAXQ];
std::vector< std::pair<int,int> > graph[MAXN];
std::map<int,int> newNum;

bool isInQueries(int x, int len)
{
	int left = 0, right = len-1, middle;

	while( (right - left) > 1 )
	{
		middle = (left+right+1)/2;
		if(queries[middle] < x) left = middle;
		else right = middle;
	}

	if(queries[left] == x) return true;
	if(queries[right] == x) return true;
	return false;
}

int main()
{
	queriesNo = NumberOfQueries();
	for(int i = 0; i < queriesNo; ++i)
	{
		queries[2*i] = QueryFrom(i+1);
		queries[2*i+1] = QueryTo(i+1);
	}

	std::sort(queries,queries+2*queriesNo);
	int prevNode = -1, index = 0;
	for(int i = 0; i < 2*queriesNo; ++i)
	{
		if(queries[i] == prevNode) continue;
		queries[index++] = queries[i];
		prevNode = queries[i];
	}

	if(MyNodeId() == 0)
	{
		for(int i = 0; i < index; ++i)
			newNum[queries[i]] = i;
	}

	int currIndex = 0;
	int nodes = NumberOfNodes();
	int partSize = (2*index)/nodes, startPoint = partSize * MyNodeId();
	if(MyNodeId() == nodes-1) partSize += (2*index) % nodes;

	for(int i = 0; i < partSize; ++i)
	{
		currIndex = startPoint + i;
		int length = 1, tmp1, tmp2, tmp3;
		int prevStudent = queries[currIndex/2],currStudent = currIndex%2 ? FirstNeighbor(prevStudent) : SecondNeighbor(prevStudent);
		while(!isInQueries(currStudent,index))
		{
			tmp1 = FirstNeighbor(currStudent); tmp2 = SecondNeighbor(currStudent);
			tmp3 = prevStudent; prevStudent = currStudent;
			currStudent = tmp3 == tmp1 ? tmp2 : tmp1;
			length++;
		}
		PutInt(0,queries[currIndex/2]);
		PutInt(0,currStudent);
		PutInt(0,length);
		Send(0);
	}

	if(MyNodeId() == 0)
	{
		for(int i = 0; i < 2*index; ++i)
		{
			int instance = Receive(-1), a = GetInt(instance), b = GetInt(instance), len = GetInt(instance);
			graph[newNum[a]].push_back(std::make_pair(newNum[b],len));
			graph[newNum[b]].push_back(std::make_pair(newNum[a],len));
		}

		int m = NumberOfQueries(), totalStudents = NumberOfStudents();

		for(int i = 1; i <= m; ++i)
		{
			int a = newNum[QueryFrom(i)], b = newNum[QueryTo(i)], currLength = 0, prevNode = -1, currNode = a;
			while(currNode != b)
			{
				for(int j = 0; j < graph[currNode].size(); ++j)
					if(graph[currNode][j].st != prevNode)
					{
						currLength += graph[currNode][j].nd;
						prevNode = currNode;
						currNode = graph[currNode][j].st;
						break;
					}
			}
			printf("%d\n", std::min(totalStudents - currLength, currLength));
		}
	}
}