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;
      |                       ^~~~~~~
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){
      |     ^~~

#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;
pii dp[mxn];
vo<vi> tbl;
map<int, set<int>> order; //all comps of val=key;

int compress(int a, int b){
    return a*c + b;
}

struct dsu{
    vi par, siz, val, conEdge;
    vo<set<int>> nei;
    dsu(int n): par(n), siz(n, 1), val(n), nei(n), conEdge(n, 0){
        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];
        }
    }
};
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;
}
bool walk(int a, int b, int val){
    priority_queue<array<int, 3>> pq;
    pq.push({tbl[a][b], a, b});
    int target = val;
    vo<vi> vis(r, vi(c, 0));
    while(pq.size()){
        auto [val, a, b] = pq.top(); pq.pop();
        if(vis[a][b]) continue;
        if(val < target) return 0;

        vis[a][b] = 1;
        target--;
        if(target<=0) return 1;

        for(auto x: dir){
            int nr = x[0]+a, nc = x[1]+b;
            if(ir(nr, nc) && !vis[nr][nc]){
                pq.push({tbl[nr][nc], nr, nc});
            }
        }
    }
    return 0;
}

// bool f(int val){
//     dsu g(r*c);
//     for(auto [i, u]: kant){
//         if(walk(i, u, val)) return 1;
//     }
//     return 0;
// }

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]){
                        g.nei[a].insert(b); 

                    }
                    else if(tbl[nr][nc] >= tbl[i][u]){
                        g.nei[b].insert(a);
                    }
                }
            }
        }
    }

    for(auto size: order){
        for(auto x: size.se){ //x should already be comp par?
            for(auto neigh: g.nei[x]){
                pii pre = dp[neigh]; //tmp and max connected to edge
                dp[x].fi = max(dp[x].fi, min(g.val[x], pre.fi + g.siz[x]));

                dp[x].se = max(pre.se, dp[x].se);
                if(g.conEdge[x]) dp[x].se = g.val[x];
                ans = max(ans, min(dp[x].se, dp[x].fi));
            }
        }
    }

    cout << ans;

    // int lo = 0, hi = 2e5+4;
    // while(hi-lo>1){
    //     int mid = (hi+lo)/2;
    //     if(f(mid)) lo = mid;
    //     else hi = mid;
    // }
    // cout << lo;
}

Test 1

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 2

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 3

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 4

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 5

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 6

Group: 1, 5, 6

Verdict: ACCEPTED

Test 7

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 8

Group: 1, 5, 6

Verdict: WRONG ANSWER

Test 9

Group: 1, 2, 5, 6

Verdict: ACCEPTED

Test 10

Group: 2, 6

Verdict: ACCEPTED

Test 11

Group: 2, 6

Verdict: ACCEPTED

Test 12

Group: 2, 6

Verdict: ACCEPTED

Test 13

Group: 2, 6

Verdict: ACCEPTED

Test 14

Group: 2, 6

Verdict: ACCEPTED

Test 15

Group: 2, 6

Verdict: ACCEPTED

Test 16

Group: 2, 6

Verdict: ACCEPTED

Test 17

Group: 2, 6

Verdict: ACCEPTED

Test 18

Group: 2, 6

Verdict: ACCEPTED

Test 19

Group: 2, 6

Verdict: ACCEPTED

Test 20

Group: 2, 6

Verdict: ACCEPTED

Test 21

Group: 2, 6

Verdict: ACCEPTED

Test 22

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 23

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 24

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 25

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 26

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 27

Group: 3, 4, 5, 6

Verdict: WRONG ANSWER

Test 28

Group: 4, 6

Verdict: WRONG ANSWER

Test 29

Group: 4, 6

Verdict: WRONG ANSWER

Test 30

Group: 4, 6

Verdict: WRONG ANSWER

Test 31

Group: 4, 6

Verdict: WRONG ANSWER

Test 32

Group: 4, 6

Verdict: ACCEPTED

Test 33

Group: 4, 6

Verdict: WRONG ANSWER

Test 34

Group: 4, 6

Verdict: WRONG ANSWER

Test 35

Group: 5, 6

Verdict: WRONG ANSWER

Test 36

Group: 5, 6

Verdict: WRONG ANSWER

Test 37

Group: 5, 6

Verdict: WRONG ANSWER

Test 38

Group: 5, 6

Verdict: WRONG ANSWER

Test 39

Group: 5, 6

Verdict: ACCEPTED

Test 40

Group: 5, 6

Verdict: WRONG ANSWER

Test 41

Group: 5, 6

Verdict: WRONG ANSWER

Test 42

Group: 6

Verdict: WRONG ANSWER

Test 43

Group: 6

Verdict: WRONG ANSWER

Test 44

Group: 6

Verdict: WRONG ANSWER

Test 45

Group: 6

Verdict: WRONG ANSWER

Test 46

Group: 6

Verdict: ACCEPTED

Test 47

Group: 6

Verdict: WRONG ANSWER

Test 48

Group: 6

Verdict: WRONG ANSWER