[Link] https://www.acmicpc.net/problem/16234
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
#include <algorithm>
#include <iostream>
#include <vector>
// #include <bits/stdc++.h>
using namespace std;
#define for0(i, n) for(int i = 0; i < n; i++)
#define for1(i, n) for(int i = 1; i <= n; i++)
#define fori(s, e) for(int i = s; i < e; i++)
typedef long long ll;
const int INF = 987654321;
int n, l, r;
int a[100][100];
int dayCnt = 0;
int di[2] = { 1, 0 };
int dj[2] = { 0, 1 };
int uni[2500];
int sum[2500];
int nation_num[2500];
void clear() {
for0(i, n*n) uni[i] = i, nation_num[i] = 0, sum[i] = 0;
}
int union_get(int point) {
if(uni[point] == point) return point;
return uni[point] = union_get(uni[point]);
}
void unify(int ai, int aj, int bi, int bj) {
int p1 = n*ai + aj, p2 = n*bi + bj;
// cout << p1 << " unify " << p2 << endl;
int u1 = union_get(p1), u2 = union_get(p2);
if(u1 < u2) uni[u2] = u1;
else uni[u1] = u2;
}
void solve() {
while(true) {
clear();
bool border_open = false;
for0(i, n) {
for0(j, n) {
for0(k, 2) {
if(i+di[k] >= n || j+dj[k] >= n) continue;
int diff = abs(a[i][j] - a[i+di[k]][j+dj[k]]);
if(l <= diff && diff <= r) {
unify(i, j, i + di[k], j + dj[k]);
border_open = true;
}
}
}
}
if(border_open == false) break;
for0(i, n) {
for0(j, n) {
int union_idx = union_get(n*i + j);
sum[union_idx] += a[i][j];
nation_num[union_idx]++;
}
}
for0(i, n * n) {
int ci = i / n, cj = i - n * ci;
a[ci][cj] = sum[union_get(i)] / nation_num[union_get(i)];
}
dayCnt++;
}
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
solve();
cout << dayCnt;
return 0;
}