poder.cpp

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

vector<vector<pair<int,int>>> pai;
vector<vector<int>> resp;

vector<vector<priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>>>> vis, nome;

pair<int,int> achar(pair<int,int> i){
    if(pai[i.first][i.second]==i)return i;
    return pai[i.first][i.second]=achar(pai[i.first][i.second]);
}

void juntar(pair<int,int> a, pair<int,int> b){
    a=achar(a);
    b=achar(b);

    if(a==b)return;

    if(nome[a.first][a.second].size()<nome[b.first][b.second].size())swap(a, b);
    resp[a.first][a.second]+=resp[b.first][b.second];
    pai[b.first][b.second]=a;
    while(vis[b.first][b.second].size()){
        vis[a.first][a.second].push(vis[b.first][b.second].top());
        vis[b.first][b.second].pop();
    }
    while(nome[b.first][b.second].size()){
        nome[a.first][a.second].push(nome[b.first][b.second].top());
        nome[b.first][b.second].pop();
    }
}

int32_t main(){
    ios_base::sync_with_stdio(0); cin.tie(0);
    int n, m;
    cin >> n >> m;
    vector<vector<int>> mapa(n+3), sol(n+3);
    vis.resize(n+3);
    nome.resize(n+3);
    pai.resize(n+3);
    resp.resize(n+3);
    for(int i=0; i<n; i++){
        mapa[i].resize(m+3);
        sol[i].resize(m+3);
        vis[i].resize(m+3);
        nome[i].resize(m+3);
        pai[i].resize(m+3);
        resp[i].resize(m+3);
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cin >> mapa[i][j];
        }
    }

    priority_queue<pair<int,pair<int,int>>, vector<pair<int,pair<int,int>>>, greater<pair<int,pair<int,int>>>> ordem;

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            ordem.push({mapa[i][j], {i, j}});
            if(i>0)vis[i][j].push({mapa[i-1][j], {i-1, j}});
            if(i+1<n)vis[i][j].push({mapa[i+1][j], {i+1, j}});
            if(j>0)vis[i][j].push({mapa[i][j-1], {i, j-1}});
            if(j+1<m)vis[i][j].push({mapa[i][j+1], {i, j+1}});
            nome[i][j].push({-1, {i, j}});
            pai[i][j]=make_pair(i, j);
            resp[i][j]=mapa[i][j];
        }
    }

    while(ordem.size()){
        pair<int,int> cur=ordem.top().second;
        if(cur!=achar(cur) || resp[cur.first][cur.second]!=ordem.top().first){
            ordem.pop();
            continue;
        }
        ordem.pop();
        if(vis[cur.first][cur.second].empty() || resp[cur.first][cur.second]<vis[cur.first][cur.second].top().first){
            while(nome[cur.first][cur.second].top().first==-1){
                pair<int,int> atual=nome[cur.first][cur.second].top().second;
                nome[cur.first][cur.second].pop();
                sol[atual.first][atual.second]=resp[cur.first][cur.second];
                nome[cur.first][cur.second].push({sol[atual.first][atual.second], atual});
            }
            continue;
        }
        pair<int,int> aux=vis[cur.first][cur.second].top().second;
        vis[cur.first][cur.second].pop();
        juntar(cur, aux);
        cur=achar(cur);
        ordem.push({resp[cur.first][cur.second], cur});
    }

    for(int i=0; i<n; i++){
        for(int j=0; j<m; j++){
            cout << sol[i][j];
            if(j!=m-1)cout << ' ';
        }
        cout << '\n';
    }

    return 0;
}