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
#include <cstdio>
#include <vector>
#include <cmath>
#include "message.h"
#include "sabotaz.h"
using namespace std;
int parent[2000005], k, n, m, e, f;
vector < int > do_wyslania, odebrane, drzewo, kr[200005];
int order[200005], order_range[200005], min_order[200005], max_order[200005], next_nr = 1;
int odw[200005];
int odp = 0;
bool *used;
int find(int a){
    if (parent[a] == a){
        return a;
    }
    else {
        parent[a] = find(parent[a]);
        return parent[a];
    }
}
void _union(int a, int b){
    a = find(a);
    b = find(b);
    parent[a] = b;
}
void wyslij(int target){
    PutInt(target, do_wyslania.size());
    int pos = 0;
    while (pos < do_wyslania.size()){
        int zakres = min((int)do_wyslania.size() - pos, 60000);
        PutInt(target, zakres);
        for (int i = pos; i < pos + zakres; i++){
            PutInt(target, do_wyslania[i]);
        }
        Send(target);
        pos += zakres;
    }
}
void odbierz(int target){
    Receive(target);
    int size = GetInt(target);
    int sum = 0;
    while (sum < size){
        int porcja = GetInt(target);
        for (int i = 0; i < porcja; i++){
            odebrane.push_back(GetInt(target));
        }
        sum += porcja;
        if (sum < size)
            Receive(target);
    }
}
void dfs(int start, int pop){
    odw[start] = 1;
    order_range[start] = next_nr;
    for (int i = 0; i < kr[start].size(); i++){
        if (kr[start][i] != pop){
            dfs(kr[start][i], start);
        }
    }
    order[start] = next_nr;
    min_order[start] = order_range[start];
    max_order[start] = order[start];
    next_nr++;
}
void dfs2(int start, int pop){
    odw[start] = 2;
    for (int i = 0; i < kr[start].size(); i++){
        if (kr[start][i] != pop){
            dfs2(kr[start][i], start);
            min_order[start] = min(min_order[start], min_order[ kr[start][i] ]);
            max_order[start] = max(max_order[start], max_order[ kr[start][i] ]);
        }
    }
    if ((min_order[start] < order_range[start]) || (max_order[start] > order[start])){
    }
    else if (pop != -1){
        odp++;
    }
}
int main(){
    n = NumberOfIsles();
    m = NumberOfBridges();
    k = min((int)NumberOfNodes(), (int)sqrt(m/n) + 1);
    if (MyNodeId() < k){
        e = MyNodeId() * (long long)m / k;
        f = (MyNodeId()+1) * (long long)m / k - 1;
        for (int i = 1; i <= n; i++){
            parent[i] = i;
        }
        used = new bool [f-e+5];
        for (int i = e; i <= f; i++){
            used[i-e] = false;
            int a = BridgeEndA(i) + 1;
            int b = BridgeEndB(i) + 1;
            if (find(a) != find(b)){
                _union(a,b);
                do_wyslania.push_back(i);
            }
        }
        if (MyNodeId() > 0){
            wyslij(0);
            do_wyslania.clear();
            odbierz(MyNodeId()-1);
            for (int i = 0; i < odebrane.size(); i++){
                do_wyslania.push_back(odebrane[i]);
            }
            if (MyNodeId() < k-1){
                wyslij(MyNodeId()+1);
            }
            do_wyslania.clear();
            for (int i = 0; i < odebrane.size(); i++){
                int a = BridgeEndA( odebrane[i] ) + 1;
                int b = BridgeEndB( odebrane[i] ) + 1;
                kr[a].push_back(b);
                kr[b].push_back(a);
                if ((odebrane[i] >= e) && (odebrane[i] <= f))
                    used[odebrane[i]-e] = true;
            }
            odebrane.clear();
        }
        else {
            for (int i = 1; i < k; i++){
                odbierz(i);
                for (int j = 0; j < odebrane.size(); j++){
                    int a = BridgeEndA( odebrane[j] ) + 1;
                    int b = BridgeEndB( odebrane[j] ) + 1;
                    if (find(a) != find(b)){
                        _union(a,b);
                        do_wyslania.push_back( odebrane[j] );
                    }
                }
                odebrane.clear();
            }
            if (k > 1){
                wyslij(1);
            }
            for (int i = 0; i < do_wyslania.size(); i++){
                int a = BridgeEndA( do_wyslania[i] ) + 1;
                int b = BridgeEndB( do_wyslania[i] ) + 1;
                kr[a].push_back(b);
                kr[b].push_back(a);
                if ((do_wyslania[i] >= e) && (do_wyslania[i] <= f))
                    used[do_wyslania[i]-e] = true;
            }
            do_wyslania.clear();
        }
        for (int i = 1; i <= n; i++){
            if (odw[i] == 0)
                dfs(i, -1);
        }
        for (int i = e; i <= f; i++){
            int a = BridgeEndA(i) + 1;
            int b = BridgeEndB(i) + 1;
            if (!used[i-e]){
                min_order[a] = min(min_order[a], order[b]);
                max_order[a] = max(max_order[a], order[b]);
                min_order[b] = min(min_order[b], order[a]);
                max_order[b] = max(max_order[b], order[a]);
            }
        }
        if (MyNodeId() > 0){
            do_wyslania.clear();
            for (int i = 1; i <= n; i++){
                do_wyslania.push_back( min_order[i] );
            }
            wyslij(0);
            do_wyslania.clear();
            for (int i = 1; i <= n; i++){
                do_wyslania.push_back( max_order[i] );
            }
            wyslij(0);
            return 0;
        }
        else {
            for (int i = 1; i < k; i++){
                odebrane.clear();
                odbierz(i);
                for (int j = 1; j <= n; j++){
                    min_order[j] = min(min_order[j], odebrane[j-1]);
                }
                odebrane.clear();
                odbierz(i);
                for (int j = 1; j <= n; j++){
                    max_order[j] = max(max_order[j], odebrane[j-1]);
                }
            }
            for (int i = 1; i <= n; i++){
                if (odw[i] == 1)
                    dfs2(i, -1);
            }
            /*for (int i = 1; i <= n; i++){
                printf("%d %d %d %d\n", order_range[i], order[i], min_order[i], max_order[i]);
            }*/
            printf("%d\n", odp);
        }
    }
}