Thin Ice

#include <iostream>
#include <vector>
#include <algorithm>
#include <numeric>
#include <functional>
#include <set>
#include <map>
#include <queue>

using namespace std;

typedef long long int ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll, ll> pll;
typedef vector<pll> vpll;
typedef set<pll> spll;
typedef pair<pll, ll> ppll_ll;
typedef set<ppll_ll> sppll_ll;
typedef set<ll> sll;

#define rep(i, a, b) for (ll i = a; i < b; i++)
#define sz(a) (ll) a.size()
#define mp(a, b) make_pair(a, b)
#define pb(a) push_back(a)
#define trav(itr, a, t) for (t::iterator itr = a.begin(); itr != a.end())

// coordinate convention (y, x) for (n, m)

const pll delta[4] = {mp(1, 0), mp(0, 1), mp(-1, 0), mp(0, -1)};

ll n, m, d;

vvll ice;

bool inline is_edge(const pll& pos) {return (pos.first == 0) || (pos.first == n - 1) || (pos.second == 0) || (pos.second == m - 1);}
ll inline coco(pll z) {return z.first + (z.second * n);}
pll inline rev_coco(ll z) {return mp(z % n, z / n);}

pll inline operator+(const pll& lhs, const pll& rhs) {return mp(lhs.first + rhs.first, lhs.second + rhs.second);}
pll inline operator+(const pll& lhs, const ll& rhs) {return mp(lhs.first + rhs, lhs.second);}

sppll_ll best_edges; // ((d[neigh] + cnt, neigh), src)
spll best_comp; // (cnt, src)

struct component;
vector<component> comps;
vll par;

ll find_par(ll x) {
    if (x != par[x]) par[x] = find_par(par[x]);
    return par[x];
}

struct component {
    ll root;
    ll cnt;
    spll edges; // (d[neigh], neigh)
    //sll members;
    component(ll root) : root(root), cnt(1) {
        par[root] = root;
        //members.insert(root);
    }
    ppll_ll best_edge() {
        return mp(*edges.rbegin() + cnt, root);
    }
    void add_best_edge() {
        if (sz(edges)) best_edges.insert(best_edge());
    }
    void absorb(ll oth) {
        //cout << "root " << root << endl;

        if (sz(edges)) best_edges.erase(best_edge()); // remove previous best edge
        best_comp.erase(mp(cnt, root));

        //cout << oth << " -> " << find_par(oth) << endl;
        oth = find_par(oth);

        if (sz(comps[oth].edges)) best_edges.erase(comps[oth].best_edge()); // remove previous best edge from oth
        best_comp.erase(mp(comps[oth].cnt, oth));
        
        par[oth] = root;
        cnt += comps[oth].cnt;
        //cout << "cnt -> " << cnt << " (+" << comps[oth].cnt << ")" << endl; 
        edges.insert(comps[oth].edges.begin(), comps[oth].edges.end()); // merge edges
        
        add_best_edge(); // make public best edge
        best_comp.insert(mp(cnt, root));
    }
    void tick(pll edge) {
        //best_edges.erase(best_edge());
        edges.erase(edge);
        add_best_edge();
    }
};

int main() {
    cin.tie(NULL)->sync_with_stdio(false);

    cin >> n >> m;
    d = 1;
    ice.resize(n);
    rep(i, 0, n) {
        ice[i].resize(m);
        rep(j, 0, m) {
            cin >> ice[i][j];
            d = max<ll>(d, ice[i][j]);
        }
    }

    par.resize(n * m);
    //comps.reserve(n * m);

    rep(j, 0, m) {
        rep(i, 0, n) {
            comps.pb(component(coco(mp(i, j))));
        }
    }

    rep(i, 0, n) {
        rep(j, 0, m) {
            // initialize neighbors
            rep(d, 0, 4) {
                pll neigh = mp(i, j) + delta[d];
                if ((neigh.first == -1) || (neigh.first == n) || (neigh.second == -1) || (neigh.second == m)) continue; // check oob
                // add edge (i, j) -> neigh (with d = ice[neigh])
                //cout << "edge: " << coco(mp(i, j)) << " -> (" << ice[neigh.first][neigh.second] << ", " << coco(neigh) << ")" << endl;
                comps[coco(mp(i, j))].edges.insert(mp(ice[neigh.first][neigh.second], coco(neigh)));
            }

            /* if (is_edge(mp(i, j))) { // now we only consider edges from active...
                // initialize presence in best_edges and best_comp
                comps[coco(mp(i, j))].add_best_edge();
                best_comp.insert(mp(1, coco(mp(i, j))));
            } */
        }
    }

    /* cout << "par:" << endl;
    rep(i, 0, n) {
        rep(j, 0, m) {
            cout << par[coco(mp(i, j))] << " ";
        }
        cout << endl;
    } */

    d++;

    while ((best_comp.empty()) || (best_comp.rbegin()->first < d)) {
    //rep(tmp, 0, 20) {
        //if (!best_comp.empty()) cout << "comp: " << best_comp.rbegin()->first << " " << best_comp.rbegin()->second << endl;
        //if (!best_edges.empty()) cout << "edge: " << best_edges.rbegin()->first.first << " " << best_edges.rbegin()->first.second << " " << best_edges.rbegin()->second << endl;
        // check for edges to add
        if ((!best_edges.empty()) && (best_edges.rbegin()->first.first >= d)) {
            ll tmp = best_edges.rbegin()->first.first;
            // do some pre-work
            ll src = best_edges.rbegin()->second;
            ll dest = best_edges.rbegin()->first.second;
            // check if edge goes from comp to itself
            if (find_par(dest) == find_par(src)) {
                //cout << "tick" << endl;
                comps[src].tick(best_edges.rbegin()->first); // remove best edge, because it goes within itself
                best_edges.erase(mp(mp(tmp, dest), src));
            } else { // the edge merges two distinct components
                //cout << "absorb" << endl;
                comps[src].absorb(dest);
            }
        } else { // if no edges, then decrement d
            d--;

            // activate all edges with ice = d
            rep(i, 0, n) {
                rep(j, 0, m) {
                    if (is_edge(mp(i, j))) {
                        if (ice[i][j] == d) {
                            // initialize presence in best_edges and best_comp
                            comps[coco(mp(i, j))].add_best_edge();
                            best_comp.insert(mp(1, coco(mp(i, j))));
                        }
                    }
                }
            }
        }

        /* cout << "par:" << endl;
        rep(i, 0, n) {
            rep(j, 0, m) {
                cout << par[coco(mp(i, j))] << " ";
            }
            cout << endl;
        } */
    }


    cout << d << endl;

    return 0;
}

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: WRONG ANSWER

Test 10

Group: 2, 6

Verdict: ACCEPTED

Test 11

Group: 2, 6

Verdict: ACCEPTED

Test 12

Group: 2, 6

Verdict: WRONG ANSWER

Test 13

Group: 2, 6

Verdict: WRONG ANSWER

Test 14

Group: 2, 6

Verdict: WRONG ANSWER

Test 15

Group: 2, 6

Verdict: ACCEPTED

Test 16

Group: 2, 6

Verdict: WRONG ANSWER

Test 17

Group: 2, 6

Verdict: ACCEPTED

Test 18

Group: 2, 6

Verdict: WRONG ANSWER

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: 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: RUNTIME ERROR

Test 33

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

Test 34

Group: 4, 6

Verdict: TIME LIMIT EXCEEDED

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: 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: RUNTIME ERROR

Test 47

Group: 6

Verdict: TIME LIMIT EXCEEDED

Test 48

Group: 6

Verdict: TIME LIMIT EXCEEDED