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
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
#include <cstdio>
#include <vector>
#include "dzialka.h"
#include "message.h"
#define ll long long
using namespace std;
int dsu_find(int x, int *&L)
{
    return (L[x]!=x) ? L[x]=dsu_find(L[x],L) : L[x];
}
void dsu_union(int x, int y, ll &sum_all, int *&L, int *&S)
{
    x=dsu_find(x,L), y=dsu_find(y,L);
    if(x!=y){
        if(S[x]<S[y])
            swap(x,y);
        sum_all+=(1ll*(S[x]+S[y])*(S[x]+S[y]+1)/2 - 1ll*S[x]*(S[x]+1)/2 - 1ll*S[y]*(S[y]+1)/2);
        L[y]=x;
        S[x]+=S[y];
    }
}
int main()
{
    int n = NumberOfNodes(), my_id=MyNodeId(), w=GetFieldWidth(), h=GetFieldHeight();
        if(my_id==0){
                ll W=w, w0=0, w1=((my_id+1)*w)/n, w=w1-w0;
                int **T;
                if(w!=0){
                    T = new int*[w];
                    for(int i=0; i<w; i++)
                        T[i] = new int[h];
                    for(int i=0; i<w; i++)
                        for(int j=0; j<h; j++)
                            T[i][j] = IsUsableCell(i+w0,j);
                }

                ll ans=0, sum_all=0;
                Receive(my_id+1);                   //Message of size h ints and 1 long long int
                ll P[h];
                for(int j=0; j<h; j++)
                    P[j] = GetInt(my_id+1);
                ans += GetLL(my_id+1);

                if(w!=0){
                        for(int j=0; j<h; j++)
                            T[w-1][j] = (T[w-1][j]==0) ? 0 : P[j]+1;
                        for(int i=w-2; i>=0; i--)
                            for(int j=0; j<h; j++)
                                T[i][j] = (T[i][j]==0) ? 0 : T[i+1][j]+1;

                        vector < vector <int> > V(W+1);
                        for(int i=0; i<w; i++)
                            for(int j=0; j<h; j++)
                                V[T[i][j]].push_back(i*h+j);
                        for(int i=0; i<w; i++)
                            delete T[i];
                        int *L = new int[w*h]; int *S = new int[w*h];
                        for(int i=0; i<w; i++)
                            for(int j=0; j<h; j++)
                                L[i*h+j]=-1;

                        int i, j;
                        for(int v=W; v>=1; v--){
                            for(int k=0; k<V[v].size(); k++){
                                i=V[v][k]/h, j=V[v][k]%h;
                                sum_all++;
                                L[i*h+j]=i*h+j;
                                S[i*h+j]=1;
                                if(j+1<h && L[i*h+j+1]!=-1)
                                    dsu_union(i*h+j,i*h+j+1,sum_all,L,S);
                                if(j-1>=0 && L[i*h+j-1]!=-1)
                                    dsu_union(i*h+j-1,i*h+j,sum_all,L,S);
                            }
                            ans+=sum_all;
                        }
                }

                printf("%lld\n",ans);
        }


        if(my_id==n-1){
                ll W=w, w0=(my_id*w)/n, w1=W, w=w1-w0;
                int **T;
                if(w!=0){
                    T = new int*[w];
                    for(int i=0; i<w; i++)
                        T[i] = new int[h];
                    for(int i=0; i<w; i++)
                        for(int j=0; j<h; j++)
                            T[i][j] = IsUsableCell(i+w0,j);
                }

                ll ans=0, sum_all=0; int P[h];
                for(int j=0; j<h; j++)
                    P[j]=0;
                if(w==0){
                        for(int j=0; j<h; j++)
                            PutInt(my_id-1,P[j]);
                        PutLL(my_id-1,ans);
                        Send(my_id-1);
                }
                else {
                        for(int i=w-2; i>=0; i--)
                            for(int j=0; j<h; j++)
                                T[i][j] = (T[i][j]==0) ? 0 : T[i+1][j]+1;

                        vector < vector <int> > V(W+1);
                        for(int i=0; i<w; i++)
                            for(int j=0; j<h; j++)
                                V[T[i][j]].push_back(i*h+j);
                        for(int j=0; j<h; j++)
                            PutInt(my_id-1,T[0][j]);
                        for(int i=0; i<w; i++)
                            delete T[i];
                        int *L = new int[w*h]; int *S = new int[w*h];
                        for(int i=0; i<w; i++)
                            for(int j=0; j<h; j++)
                                L[i*h+j]=-1;

                        int i, j;
                        for(int v=W; v>=1; v--){
                            for(int k=0; k<V[v].size(); k++){
                                i=V[v][k]/h, j=V[v][k]%h;
                                sum_all++;
                                L[i*h+j]=i*h+j;
                                S[i*h+j]=1;
                                if(j+1<h && L[i*h+j+1]!=-1)
                                    dsu_union(i*h+j,i*h+j+1,sum_all,L,S);
                                if(j-1>=0 && L[i*h+j-1]!=-1)
                                    dsu_union(i*h+j-1,i*h+j,sum_all,L,S);
                            }
                            ans+=sum_all;
                        }

                        PutLL(my_id-1,ans);
                        Send(my_id-1);
                }

        }


        if(my_id!=0 && my_id!=n-1){
                ll W=w, w0=(my_id*w)/n, w1=((my_id+1)*w)/n, w=w1-w0;
                int **T;
                if(w!=0){
                    T = new int*[w];
                    for(int i=0; i<w; i++)
                        T[i] = new int[h];
                    for(int i=0; i<w; i++)
                        for(int j=0; j<h; j++)
                            T[i][j] = IsUsableCell(i+w0,j);
                }


                ll ans=0, sum_all=0;
                Receive(my_id+1);                   //Message of size h ints and 1 long long int
                int P[h];
                for(int j=0; j<h; j++)
                    P[j] = GetInt(my_id+1);
                ans += GetLL(my_id+1);
                if(w==0){
                        for(int j=0; j<h; j++)
                            PutInt(my_id-1,P[j]);
                        PutLL(my_id-1,ans);
                        Send(my_id-1);
                }
                else {
                        for(int j=0; j<h; j++)
                            T[w-1][j] = (T[w-1][j]==0) ? 0 : P[j]+1;
                        for(int i=w-2; i>=0; i--)
                            for(int j=0; j<h; j++)
                                T[i][j] = (T[i][j]==0) ? 0 : T[i+1][j]+1;

                        vector < vector <int> > V(W-w0+1);
                        for(int i=0; i<w; i++)
                            for(int j=0; j<h; j++)
                                V[T[i][j]].push_back(i*h+j);
                        for(int j=0; j<h; j++)
                            PutInt(my_id-1,T[0][j]);
                        for(int i=0; i<w; i++)
                            delete T[i];
                        int *L = new int[w*h]; int *S = new int[w*h];
                        for(int i=0; i<w; i++)
                        for(int j=0; j<h; j++)
                            L[i*h+j]=-1;

                        int i, j;
                        for(int v=W-w0; v>=1; v--){
                            for(int k=0; k<V[v].size(); k++){
                                i=V[v][k]/h, j=V[v][k]%h;
                                sum_all++;
                                L[i*h+j]=i*h+j;
                                S[i*h+j]=1;
                                if(j+1<h && L[i*h+j+1]!=-1)
                                    dsu_union(i*h+j,i*h+j+1,sum_all,L,S);
                                if(j-1>=0 && L[i*h+j-1]!=-1)
                                    dsu_union(i*h+j-1,i*h+j,sum_all,L,S);
                            }
                            ans+=sum_all;
                        }

                        PutLL(my_id-1,ans);
                        Send(my_id-1);
                }

        }
    return 0;
}