Thin Ice

input/code.cpp: In constructor 'dsu::dsu(long long int)':
input/code.cpp:46:18: warning: 'dsu::nei' will be initialized after [-Wreorder]
   46 |     vo<set<int>> nei;
      |                  ^~~
input/code.cpp:45:23: warning:   'vi dsu::conEdge' [-Wreorder]
   45 |     vi par, siz, val, conEdge, compind;
      |                       ^~~~~~~
input/code.cpp:47:5: warning:   when initialized here [-Wreorder]
   47 |     dsu(int n): par(n), siz(n, 1), val(n), nei(n), conEdge(n, 0), compind(n, -1){
      |     ^~~

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define vo vector
#define pb push_back
#define se second
#define fi first
#define sz(x) x.size()
typedef long long ll;
typedef vector<int> vi;
typedef pair<int, int> pii;
#define umap unordered_map
#define uset unordered_set
 
#define rep(i, a, b) for(ll i=(a); i<b; i++)
#define pr1(x) cerr << #x << '=' << x << ' ';
//for google contests
#define all(v) v.begin(), v.end()
#define repd(i, a, b) for(ll i=(b-1); i >= a; i--)
void _pr(signed x) {cerr << x;}
void _pr(long long x) {cerr << x;}
void _pr(unsigned long long x) {cerr << x;}
void _pr(double x) {cerr << x;}
void _pr(char x) {cerr << '\'' << x << '\'';}
void _pr(const char* x) {cerr << x;}
void _pr(bool x) {cerr << (x ? "true" : "false");}
template<typename T, typename V> void _pr(const pair<T, V> &x);
template<typename T, typename V> void _pr(const pair<T, V> &x) {cerr << "\e[95m" << "[ "; _pr(x.first); cerr << ", "; _pr(x.second); cerr << "\e[95m" << ']';}
template<typename T> void _pr(const T &x) {int F=0; cerr << '{'; for(auto &i: x) cerr << (F++ ? ", " : ""), _pr(i); cerr << "\e[91m" << '}';}
template <typename T, typename... V> void _pr(T t, V... v) {_pr(t); if(sizeof...(v)) cerr << ", "; _pr(v...);}
#define pr(x...) cerr << "\e[91m" << __func__ << ':' << __LINE__ << " [" << #x << "] = ["; _pr(x); cerr << "\e[91m" << ']' << "\033[0m"  << endl;
 
//go for outline with ;, then details
ll const inf = LLONG_MAX, mxn = 2e5+4;
int r, c, ans, val[mxn], siz[mxn], conEdge[mxn], add[mxn], solesiz[mxn];
set<int> dp[mxn];
vo<vi> tbl;
map<int, set<int>, greater<int>> order; //all comps of val=key;
 
int compress(int a, int b){
    return a*c + b;
}
 
struct dsu{
    vi par, siz, val, conEdge, compind;
    vo<set<int>> nei;
    dsu(int n): par(n), siz(n, 1), val(n), nei(n), conEdge(n, 0), compind(n, -1){
        rep(i, 0, n) par[i] = i;
    }
    int findpar(int v){
        if(v==par[v]) return v;
        return par[v] = findpar(par[v]);
    }
    void unite(int a, int b){
        a = findpar(a), b = findpar(b);
        if(a!=b){
            if(siz[b] > siz[a]) swap(a, b);
            par[b] = a;
            siz[a] += siz[b]; siz[b] = 0;
            conEdge[a] |= conEdge[b];
            compind[a] = max(compind[a], compind[b]); //eeeh?
        }
    }
};
int dir[4][2] = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool ir(int a, int b){
    return a>=0&&b>=0&&a<r&&b<c;
}
 
signed main(){
    cin.tie(0)->sync_with_stdio(0);
    cin>>r>>c; 
    tbl.assign(r, vi(c, 0));
    dsu g(r*c);
    rep(i, 0, r){
        rep(u, 0, c){
            cin>>tbl[i][u];
            if(i==0 || u==0 || i==r-1 || u==c-1) g.conEdge[compress(i, u)] = 1;
        }
    }
 
    rep(i, 0, r){
        rep(u, 0, c){
            for(auto [nr, nc]: dir){
                nr+=i, nc+=u;
                if(ir(nr, nc) && tbl[i][u] == tbl[nr][nc]){
                    g.unite(compress(nr, nc), compress(i, u));
                }
            }
        }
    }
    rep(i, 0, r){
        rep(u, 0, c){
            int b = compress(i, u); b=g.findpar(b); g.val[b] = tbl[i][u];
            order[tbl[i][u]].insert(b);
            for(auto [nr, nc]: dir){
                nr+=i, nc+=u;
                if(ir(nr, nc)){
                    int a = compress(nr, nc);
                    a = g.findpar(a);
                    if(tbl[i][u] >= tbl[nr][nc]){ //större grannar
                        g.nei[a].insert(b); 
 
                    }
                    if(tbl[nr][nc] >= tbl[i][u]){
                        g.nei[b].insert(a);
                    }
                }
            }
        }
    }

    //find all indirect and direct smaller comps neighbours
    int compind = 0;
    for(auto size: order){
        set<array<int, 3>> prevnei;
        //find compind to assign new dp
        for(auto x: size.se){ 
            prevnei.insert({x, -1, 0});
            for(auto neigh: g.nei[x]){
                neigh = g.findpar(neigh);
                prevnei.insert({neigh, g.compind[neigh], g.siz[neigh]});
            }
        }
        for(auto x: size.se){
            x = g.findpar(x);
            prevnei.insert({x, g.compind[x], g.siz[x]});
        }
        
        for(auto x: size.se){ //neigh is bigger
            for(auto neigh: g.nei[x]){
                g.unite(neigh, x);
            }
        }
        //need to add if x has no neighbours
        
        map<int, int> newcompind;
        for(auto [neigh, prevcompind, prevsiz]: prevnei){
            pr(size.fi, neigh, prevcompind, compind)
            int nw = g.findpar(neigh);
            if(newcompind.count(nw)){
                if(prevcompind != -1) 
                    dp[prevcompind].insert(newcompind[nw]);
            }
            else{
                if(prevcompind != -1)
                    dp[prevcompind].insert(compind);
                newcompind[nw] = compind;
                g.compind[nw] = compind;
                val[compind] = size.fi;
                siz[compind] = g.siz[nw];
                conEdge[compind] = g.conEdge[nw];

                compind++;
            }
        }
    }

    //just go through comps increasing order
    // add saves each comps tmp val

    repd(ind, 0, compind){
        // pr(ind, dp[ind])
        if(dp[ind].size()==0) add[ind] = min(val[ind], solesiz[ind]);

        for(auto childind: dp[ind]){ //add saves best val until child
            add[ind] = max(add[ind], min(val[childind], add[childind] + siz[childind] - siz[ind]));

            if(conEdge[ind]) ans = max(ans, min(val[ind], add[ind] + siz[ind]));
        }
        // pr(dp[ind], add[ind], siz[ind], val[ind])
    }
 
    cout << ans;
}
/*
4 4
9 11 5 7
7 9 14 3
1 3 2 3
11 4 14 8

3 5
1 11 1 3 5
4 12 7 8 7
13 14 14 9 4

10 1
2 2 1 3 1 1 1 2 1 2

om varja komponent innehåller rutor av samma nivå. 
aktivera en komponent och kolla efter komponenter av mindre nivå (som ska vara mergade) som
kan nås antingen direkt eller indirekt via rutor av högre nivå.

de mindre nivå komponterna har ett eget bästa svar : min(val[comp], compsize after merged with bigger/equal)
de mindre nivå komponenterna har ett tmp värde: min(val[comp], prevtmp + compsize) 

vi kan använda tmp värdet

för hitta dessa grannar: precomputa genom att merga större med mindre och skapa kanter mellan nya komponent och gamla komponents
information, information är allt som behövs. 

gör samma sak i början men spara barn i parcomps och ej rev
vid merge, prevcompind.insert(newcompind)
*/

Test 1

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [14, 6, -1, 0]
main:1...

Test 2

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [13, 10, -1, 0]
main:...

Test 3

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [8, 8, -1, 0]
main:13...

Test 4

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [14, 12, -1, 0]
main:...

Test 5

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [13, 14, -1, 0]
main:...

Test 6

Group: 1, 5, 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [14, 5, -1, 0]
main:1...

Test 7

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [12, 4, -1, 0]
main:1...

Test 8

Group: 1, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [16, 9, -1, 0]
main:1...

Test 9

Group: 1, 2, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [5, 5, -1, 0]
main:13...

Test 10

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 11

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 12

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 13

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 14

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 15

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 16

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 17

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 18

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 19

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 20

Group: 2, 6

Verdict: TIME LIMIT EXCEEDED

Test 21

Group: 2, 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [3, 447, -1, 0]
main:...

Test 22

Group: 3, 4, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [100, 13, -1, 0]
main...

Test 23

Group: 3, 4, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [79, 96, -1, 0]
main:...

Test 24

Group: 3, 4, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [100, 7, -1, 0]
main:...

Test 25

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [83, 1, -1, 0]
main:1...

Test 26

Group: 3, 4, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [95, 29, -1, 0]
main:...

Test 27

Group: 3, 4, 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [100, 95, -1, 0]
main...

Test 28

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 29

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 30

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 31

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 32

Group: 4, 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [198270, 1, -1, 0]
ma...

Test 33

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 35

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [1000, 487, -1, 0]
ma...

Test 36

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [1000, 314, -1, 0]
ma...

Test 37

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [688, 72, -1, 0]
main...

Test 38

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [995, 520, -1, 0]
mai...

Test 39

Group: 5, 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [977, 32, -1, 0]
main...

Test 40

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [998, 988, -1, 0]
mai...

Test 41

Group: 5, 6

Verdict: ACCEPTED

main:139 [size.fi, neigh, prevcompind, compind] = [1000, 119, -1, 0]
ma...

Test 42

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 43

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 44

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 45

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 46

Group: 6

Verdict: WRONG ANSWER

main:139 [size.fi, neigh, prevcompind, compind] = [191628, 20000, -1, 0]
[9...

Test 47

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 6

Verdict: TIME LIMIT EXCEEDED