Thin Ice

#include <iostream>
#include <vector>
#include <set>

using namespace std;

bool debug = false;

typedef long long ll;
typedef vector<ll> vll;
typedef vector<vll> vvll;
typedef pair<ll,ll> pll;
typedef set<pll> sp;
typedef vector<sp> vsp;

#define rep(a,b,c) for(ll a = b; a < c; a++)
#define rrep(a,b,c) for(ll a = c-1; a >= b; a--)
#define itr_rep(a,b,_type) for(_type::iterator a = b.begin(); a != b.end(); a++)
#define pb push_back
#define mp make_pair
#define sz size
#define all(a) a.begin(),a.end()

ll uf_parent(ll a);
ll uf_merge(ll a, ll b);
bool try_D();

ll ans;

ll n;
ll m;
vll d;
ll D; // 2 * 10^5

ll coords(ll i, ll j) {return m*i + j;}

vll uf_par;
vll uf_size;
vsp uf_border; // <d,par_id> over all active components

sp best; // <d,par_id> over all active components
// best contains the id of where it is, not where it goes.
// being an active component is the same as having
//      an element with your par_id in this set.
sp edge; // <d,id> for all things on the edge.

int main() {
    cin >> n;
    cin >> m;
    d.resize(n*m,0);
    rep(i,0,n) {
        rep(j,0,m) {
            cin >> d[coords(i,j)];
        }
    }
    D = n*m;

    // initialize uf
    uf_par.resize(n*m,0);
    rep(i,0,n*m) {uf_par[i] = i;}
    uf_size.resize(n*m,1);
    uf_border.resize(n*m,sp());
    rep(i,0,n) {
        rep(j,0,m) {
            if (i != 0) {uf_border[coords(i,j)].insert(mp(-d[coords(i-1,j)],coords(i-1,j)));}
            if (i != n-1) {uf_border[coords(i,j)].insert(mp(-d[coords(i+1,j)],coords(i+1,j)));}
            if (j != 0) {uf_border[coords(i,j)].insert(mp(-d[coords(i,j-1)],coords(i,j-1)));}
            if (j != m-1) {uf_border[coords(i,j)].insert(mp(-d[coords(i,j+1)],coords(i,j+1)));}
        }
    }

    // create edge
    rep(i,0,n) {edge.insert(mp(-d[coords(i,0)],coords(i,0)));}
    rep(i,0,n) {edge.insert(mp(-d[coords(i,m-1)],coords(i,m-1)));}
    rep(j,0,m) {edge.insert(mp(-d[coords(0,j)],coords(0,j)));}
    rep(j,0,m) {edge.insert(mp(-d[coords(n-1,j)],coords(n-1,j)));}

    best.clear();

    while (!try_D()) {D--;} // D=1 must always work

    cout << D << endl;

    if (debug) {
        ll counting = 0;
        rep(i,0,n) {
            rep(j,0,m) {
                if (uf_parent(coords(i,j)) == uf_parent(ans)) {
                    counting++;
                }
            }
        }
        cout << counting << " " << uf_size[ans] << " " << ans << " " << uf_parent(ans) << endl;
    }
    return 0;
}

bool try_D() {
    ll tmp = -1;
    ll cmp = -1;
    ll other = -1;
    while (-(*edge.begin()).first >= D) { // Introduce all edge components with d >= D
        tmp = (*edge.begin()).second;
        if (uf_par[tmp] == tmp) {
            best.insert(mp((*uf_border[tmp].begin()).first,tmp));
            //if (uf_border[tmp].empty()) {cout << "oh no" << endl;} // never triggered
        }
        edge.erase(edge.begin()); // Adding item to best is the same as activating it?
    }

    while (!best.empty()) {
        cmp = uf_parent((*best.begin()).second);
        best.erase(best.begin());
        while (-(*uf_border[cmp].begin()).first >= D - uf_size[cmp]) {
            other = uf_parent((*uf_border[cmp].begin()).second);
            uf_border[cmp].erase(uf_border[cmp].begin());
            cmp = uf_merge(cmp, other); // uf_merge deals with if the two are in the same component
            if (uf_size[cmp] >= D) {
                ans = cmp;
                return true;
            }
        } // backburner time!
        edge.insert(mp((*uf_border[cmp].begin()).first - uf_size[cmp],cmp)); // <-(d+uf_size), par_id>
    }
    return false;
}

ll uf_parent(ll a) {
    if (uf_par[a] != uf_par[uf_par[a]])  {uf_par[a] = uf_par[uf_par[a]];}
    return uf_par[a];
}

ll uf_merge(ll a, ll b) {
    ll ap = uf_parent(a);
    ll bp = uf_parent(b);
    if (ap == bp) {return ap;}
    if (uf_size[bp] > uf_size[ap]) {swap(ap,bp);}
    uf_par[bp] = ap;
    uf_size[ap] += uf_size[bp];
    if (uf_border[ap].sz() < uf_border[bp].sz()) {swap(uf_border[ap],uf_border[bp]);}
    uf_border[ap].insert(all(uf_border[bp]));
    uf_border[bp].clear();
    return ap;
}

// We build from larger to smaller, beginning at the edge.
// Hence we need to sort all the things at the edge to do
// stuff

// Consistency stuff:
// Everything within a compoent has the same parent
// This parent has a set with the cells on the border ordered by d
// It may contain cells already in the component, so this needs to be checked in every acess

// We want every component to be able to reach D.
// Hence it can add a cell iff the new call has d >= D-uf_size[cmp]. D is global. uf_size is consistent

// We always try to add the next cell with largest d over all possible merges.
// If this wasn't large enough, we put the component on the backburner.
// Backburner = components with no immediate possible merges.

// What if a new merge becomes possible for a component on the back-burner?
// This only happends when another component expands into it.
// Then the components will be merged and the non-backburner will keep being a non-backburner.

// What happends when all components have been put on the back-burner?
// Then we decrement D.
// How do we non-linearly get items back from the back-burner?
// Can we sort stuff on the back-burner such that some stuff get's back earlier?
// Then every thing goes back at most once per item.

// Something goes back when it can merge with the item. d_max >= D-uf_size, which happends when D =< d_max + uf_size.
// Hence we can use edge as the back_burner.

// After we have gone into a component and merged everything there is there,
// we add it to the back-burner as it cannot get high enough on the list in this iteration of D
// unless another compoennt merges into it, but then we only take over that spot in best.

Test 1

Group: 1, 5, 6

Verdict: ACCEPTED

Test 2

Group: 1, 5, 6

Verdict: ACCEPTED

Test 3

Group: 1, 5, 6

Verdict: ACCEPTED

Test 4

Group: 1, 5, 6

Verdict: ACCEPTED

Test 5

Group: 1, 5, 6

Verdict: ACCEPTED

Test 6

Group: 1, 5, 6

Verdict: ACCEPTED

Test 7

Group: 1, 5, 6

Verdict: ACCEPTED

Test 8

Group: 1, 5, 6

Verdict: ACCEPTED

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: ACCEPTED

Test 23

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 24

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 25

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 26

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 27

Group: 3, 4, 5, 6

Verdict: ACCEPTED

Test 28

Group: 4, 6

Verdict: WRONG ANSWER

Test 29

Group: 4, 6

Verdict: ACCEPTED

Test 30

Group: 4, 6

Verdict: ACCEPTED

Test 31

Group: 4, 6

Verdict: ACCEPTED

Test 32

Group: 4, 6

Verdict: ACCEPTED

Test 33

Group: 4, 6

Verdict: ACCEPTED

Test 34

Group: 4, 6

Verdict: WRONG ANSWER

Test 35

Group: 5, 6

Verdict: ACCEPTED

Test 36

Group: 5, 6

Verdict: ACCEPTED

Test 37

Group: 5, 6

Verdict: ACCEPTED

Test 38

Group: 5, 6

Verdict: ACCEPTED

Test 39

Group: 5, 6

Verdict: ACCEPTED

Test 40

Group: 5, 6

Verdict: ACCEPTED

Test 41

Group: 5, 6

Verdict: ACCEPTED

Test 42

Group: 6

Verdict: ACCEPTED

Test 43

Group: 6

Verdict: ACCEPTED

Test 44

Group: 6

Verdict: ACCEPTED

Test 45

Group: 6

Verdict: ACCEPTED

Test 46

Group: 6

Verdict: ACCEPTED

Test 47

Group: 6

Verdict: ACCEPTED

Test 48

Group: 6

Verdict: ACCEPTED