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

#include <algorithm>
#include <iostream>

using namespace std;

const int nax = 1e8 + 55;
int p[nax];
char s[nax];

int main() {
	int nodes = NumberOfNodes();
	assert(nodes >= 4);
	int my_id = MyNodeId();
	int n = GetLength();
	if(my_id >= 4) return 0;
	
	long long ans = 0;
	if(my_id == 0) {
		for(int i = 0; i < n; ++i) s[i] = GetLetter(i);
		int l = 0, r = 0;
		for(int i=0;i<n/2;i++)
		{
			if(i<r)
				p[i]=min(r-i+1,p[l+r-i+1]);
			int L=i-p[i], R=i+p[i]-1;
			while(L-1>=0 && R+1<n && s[L-1]==s[R+1])
				p[i]++,L--,R++;
			if(R>r) l=L,r=R;
			ans += p[i];
		}
	}
	else if(my_id == 1) {
		for(int i = 0; i < n; ++i) s[i] = GetLetter(i);
		int l = 0, r = 0;
		for(int i=0;i<n/2;i++)
		{
			if(i<r)
				p[i]=min(r-i,p[l+r-i]);
			int L=i-p[i], R=i+p[i];
			while(L-1>=0 && R+1<n && s[L-1]==s[R+1])
				p[i]++,L--,R++;
			if(R>r) l=L,r=R;
			ans += p[i] + 1;
		}
	}
	else if(my_id == 2) {
		for(int i = 0; i < n; ++i) s[n-1-i] = GetLetter(i);
		int l = 0, r = 0;
		for(int i=0;i<(n+1)/2;i++)
		{
			if(i<r)
				p[i]=min(r-i+1,p[l+r-i+1]);
			int L=i-p[i], R=i+p[i]-1;
			while(L-1>=0 && R+1<n && s[L-1]==s[R+1])
				p[i]++,L--,R++;
			if(R>r) l=L,r=R;
			ans += p[i];
		}
		
	}
	else if(my_id == 3) {
		for(int i = 0; i < n; ++i) s[n-1-i] = GetLetter(i);
		int l = 0, r = 0;
		for(int i=0;i<(n+1)/2;i++)
		{
			if(i<r)
				p[i]=min(r-i,p[l+r-i]);
			int L=i-p[i], R=i+p[i];
			while(L-1>=0 && R+1<n && s[L-1]==s[R+1])
				p[i]++,L--,R++;
			if(R>r) l=L,r=R;
			ans += p[i] + 1;
		}
	}
	if(my_id != 0) {
		PutLL(0, ans);
		Send(0);
		return 0;
	}
	for(int i = 1; i <= 3; ++i) {
		Receive(i);
		ans += GetLL(i);
	}
	printf("%lld\n", ans);
}