Submission

[PPPPPPPPPPPPPPP]

Score: 100

User: hmmm

Problemset: fireball

Language: cpp

Time: 0.002 second

Submitted On: 2025-04-06 10:30:20

#include<bits/stdc++.h>
using namespace std;
using pii=array<int,2>;
const int N=105;
int a[N][N],pa[N*N],sz[N*N];
vector<pii> p;
int dx[]={0,0,1,-1};
int dy[]={1,-1,0,0};

inline int find(int v){
    if(v==pa[v]) return v;
    return pa[v]=find(pa[v]);
}

inline void U(int u,int v){
    u=find(u);
    v=find(v);
    if(u!=v){
        if(sz[u]>sz[v]) swap(u,v);
        sz[u]+=sz[v];
        pa[v]=u;
    }
}

int main(){
    ios::sync_with_stdio(0); cin.tie(0);
    int n,m,k,ans=0;
    cin >> n >> m >> k;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            cin >> a[i][j];
            if(a[i][j]==1) ans++;
        }
    }
    for(int i=0;i<N*N;i++) pa[i]=i,sz[i]=1;;
    for(int i=1;i<=n;i++){
        for(int j=1;j<=m;j++){
            if(a[i][j]==0) continue;
            for(int t=0;t<4;t++){
                int xx=i+dx[t];
                int yy=j+dy[t];
                if(a[xx][yy]==1){
                    U(i*m+j,xx*m+yy);
                }
            }
        }
    }

    while(k--){
        int u,v;
        cin >> u >> v;
        if(a[u][v]==0) cout << ans << "\n";
        else{
            if(find(u*m+v)!=find(0)){
                ans-=sz[find(u*m+v)];
                U(0,u*m+v);
            }
            cout << ans << "\n";
        }
    }
}