Submission

Score: 100

User: Chawin

Problemset: fireball

Language: cpp

Time: 0.003 second

Submitted On: 2026-03-22 14:23:25

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

vector<int> city(10001);

int main(){
    ios_base::sync_with_stdio(0), cin.tie(0);

    int n, m, q;
    cin >> n >> m >> q;

    vector<vector<int>> mp(n+1, vector<int> (m+1));
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            cin >> mp[i][j];
        }
    }

    vector<vector<int>> com(n+1, vector<int>(m+1, 0));
    vector<vector<bool>> visited(n+1, vector<bool> (m+1, false));

    queue<pair<int, int>> qu;

    int dx[4] = {0, 0, 1, -1};
    int dy[4] = {-1, 1, 0, 0};

    int cnt = 0, cntCity = 0;
    for(int i = 1; i <= n; i++){
        for(int j = 1; j <= m; j++){
            if(mp[i][j] == 1 && !visited[i][j]){
                qu.push({i, j});

                // cout << i << " " << j << "\n";

                cnt++;

                while(!qu.empty()){
                    int r = qu.front().first;
                    int c = qu.front().second;
                    qu.pop();

                    if(visited[r][c]) continue;

                    visited[r][c] = true;
                    com[r][c] = cnt;
                    city[cnt]++;

                    for(int d = 0; d < 4; d++){
                        int nr = r + dx[d];
                        int nc = c + dy[d];

                        if(nr <= 0 || nc <= 0 || nr > n || nc > m) continue;
                        if(visited[nr][nc]) continue;
                        if(mp[nr][nc] == 0) continue;

                        qu.push({nr, nc});
                    }
                }

                cntCity += city[cnt];
            }
        }
    }

    // cout << "\n";
    // for(int i = 1; i <= n; i++){
    //     for(int j = 1; j <= m; j++){
    //         cout << com[i][j] << " ";
    //     }
    //     cout << "\n";
    // }

    vector<bool> destroy(cnt+1, false);
    while(q--){
        int x, y;
        cin >> x >> y;

        int root = com[x][y];
        if(root == 0) cout << cntCity << "\n";
        else if(destroy[root]) cout << cntCity << "\n";
        else{
            cntCity -= city[root];
            destroy[root] = true;
            cout << cntCity << "\n";
        }
    }

    return 0;
}