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
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
#include <iostream>
#include <cassert>
#include <vector>
#include <cmath>

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

using namespace std;

const int master_id = 0;
const int end_task = 0;

void master();
void shut_down_node(int node_id);
void send_task(int node_id, int task_id);

void slave();
int solve_task(int task_number);
void next(int& next, int& prev);

int main() {
	ios_base::sync_with_stdio(0);

	if (MyNodeId() == master_id) {
		master();
	} else {
		slave();
	}

	return 0;
}

// master
void master() {
	int node_count;
	int slave_count;
	int task_count;
	int sender;
	vector<int> answers;
	vector<int> tasks_allocation;
	int last_task;
	int answers_received;

	task_count = NumberOfQueries();
	node_count = NumberOfNodes();
	slave_count = node_count - 1;

	last_task = 0;
	tasks_allocation.resize(node_count);

	answers_received = 0;
	answers.resize(task_count + 1);

	for (int slave = 1; slave <= min(slave_count, task_count); ++slave) {
		++last_task;
		tasks_allocation[slave] = last_task;
		send_task(slave, last_task);
	}

	for (int slave = task_count + 1; slave <= slave_count; ++slave) {
		shut_down_node(slave);
	}

	while(answers_received < task_count){
		sender = Receive(-1);
		++answers_received;
		answers[tasks_allocation[sender]] = GetInt(sender);

		if(last_task == task_count){
			shut_down_node(sender);
		} else {
			++last_task;
			tasks_allocation[sender] = last_task;
			send_task(sender, last_task);
		}
	}

	for(int i = 1; i <= task_count; ++i){
		cout << answers[i] << endl;
	}
}

void send_task(int node_id, int task_id){
	PutInt(node_id, task_id);
	Send(node_id);
}

void shut_down_node(int node_id) {
	send_task(node_id, end_task);
}

// end master

// slave
void slave() {
	int task_number;
	int solution;

	do {
		assert(Receive(master_id) == master_id);
		task_number = GetInt(master_id);

		if (task_number != end_task) {
			solution = solve_task(task_number);
			PutInt(master_id, solution);
			Send(master_id);
		}
	} while (task_number != end_task);
}

int solve_task(int task_number) {
	int solution = 0;
	int source = QueryFrom(task_number);
	int target = QueryTo(task_number);
	int a_next, a_prev;
	int b_next, b_prev;

	if (source == target) {
		return solution;
	}

	a_next = FirstNeighbor(source);
	a_prev = source;
	b_next = SecondNeighbor(source);
	b_prev = source;
	++solution;

	while (a_next != target && b_next != target) {
		next(a_next, a_prev);
		next(b_next, b_prev);
		++solution;
	}

	return solution;
}

void next(int& next, int& prev) {
	int neighbor;

	neighbor = FirstNeighbor(next);
	if (neighbor == prev) {
		neighbor = SecondNeighbor(next);
	}
	prev = next;
	next = neighbor;
}
// end slave