Coordinate Linearization for Grid Structures

To efficiently apply disjoint set operations on a two-dimensional matrix of dimensions $H \times W$, encode each cell position $(r, c)$ into a scalar identifier using the formula $id = r \times W + c$. This mapping establishes a bijection between matrix coordinates and the integer range $[0, HW)$, eliminating the overhead of managing paired indices within the union-find structure. Decoding follows naturally: $r = id / W$ and $c = id % W$.

Disjoint Set Union with Augmented State

Represent the grid connectivity using a Union-Find structure augmented to track component properties. Maintain a representative array for parent pointers and a compMax array storing the maximal treasure value within each connected component. During initialization, each cell constitutes its own set, with compMax initialized to the grid's character value at that position.

Path Compression Optimizasion

Implement the find operation with recursive path compression to ensure amortized constant-time complexity:

int findSet(int v) {
    return representative[v] == v ? v : representative[v] = findSet(representative[v]);
}

This collapses the traversal path by linking visited nodes directly to the root representative, flattening the tree structure during queries.

Component Merging and Property Aggregation

Traverse the grid systematically. For each land cell (denoted by characters other than '0'), inspect the four adjacent cells using direction vectors $dr = {-1, 0, 1, 0}$ and $dc = {0, 1, 0, -1}$. Compute the linear index for each valid neighboring land cell.

When adjacent land cells are identified with linear indices $a$ and $b$, determine their respective set leaders $ra$ and $rb$ via the find operation. If $ra \neq rb$, merge the sets by attaching $ra$ under $rb$ (or vice versa), and synchronize the treasure data:

if (ra != rb) {
    representative[ra] = rb;
    compMax[rb] = max(compMax[ra], compMax[rb]);
}

Enumeration of Islands and Treasures

Following the union phase, enumerate all $HW$ linearized indices. For each index $i$ where representative[i] == i (indicating a root node):

• Decode the index to grid coordinates $(r, c)$
• If the terrain at $(r, c)$ is not water ('0'), increment the island counter
• If compMax[i] exceeds the character '1', indicating the presence of high-value treasures within that component, increment the treasure counter

Reference Implementation

#include <bits/stdc++.h>
using namespace std;

struct IslandDSU {
    vector<int> representative;
    vector<char> compMax;
    vector<string> terrain;
    int rows, cols;
    
    inline int linearize(int r, int c) const { 
        return r * cols + c; 
    }
    
    int findRoot(int v) {
        return representative[v] == v ? v : representative[v] = findRoot(representative[v]);
    }
    
    void build(int h, int w) {
        rows = h; cols = w;
        int total = rows * cols;
        representative.resize(total);
        compMax.resize(total);
        terrain.resize(rows);
        
        for (auto &line : terrain) cin >> line;
        
        for (int i = 0; i < total; ++i) {
            representative[i] = i;
            int r = i / cols, c = i % cols;
            compMax[i] = terrain[r][c];
        }
    }
    
    void uniteComponents() {
        const int dRow[] = {-1, 0, 1, 0};
        const int dCol[] = {0, 1, 0, -1};
        
        for (int r = 0; r < rows; ++r) {
            for (int c = 0; c < cols; ++c) {
                if (terrain[r][c] == '0') continue;
                
                int currIdx = linearize(r, c);
                for (int d = 0; d < 4; ++d) {
                    int nr = r + dRow[d], nc = c + dCol[d];
                    if (nr < 0 || nr >= rows || nc < 0 || nc >= cols) continue;
                    if (terrain[nr][nc] == '0') continue;
                    
                    int neighborIdx = linearize(nr, nc);
                    int rootCurr = findRoot(currIdx);
                    int rootNei = findRoot(neighborIdx);
                    
                    if (rootCurr != rootNei) {
                        representative[rootCurr] = rootNei;
                        compMax[rootNei] = max(compMax[rootCurr], compMax[rootNei]);
                    }
                }
            }
        }
    }
    
    pair<int, int> analyze() {
        int islandCount = 0, treasureCount = 0;
        int total = rows * cols;
        
        for (int i = 0; i < total; ++i) {
            if (representative[i] != i) continue;
            int r = i / cols, c = i % cols;
            if (terrain[r][c] == '0') continue;
            
            ++islandCount;
            if (compMax[i] > '1') ++treasureCount;
        }
        return {islandCount, treasureCount};
    }
};

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int h, w;
    cin >> h >> w;
    
    IslandDSU solver;
    solver.build(h, w);
    solver.uniteComponents();
    
    auto [islands, treasures] = solver.analyze();
    cout << islands << ' ' << treasures;
    return 0;
}