제출 #1337149

#제출 시각아이디문제언어결과실행 시간메모리
1337149nxk02102010Flooding (NOI25_flooding)C++20
12 / 100
3094 ms8472 KiB
#include <bits/stdc++.h>
using namespace std;

int main() {
   // freopen("FloodinDL.Inp","r",stdin);freopen("FloodinDL.Out","w",stdout);
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);
    int h, w;
    cin >> h >> w;
    vector<vector<char>> grid(h, vector<char>(w));
    for (int i = 0; i < h; i++) {
        string s;
        cin >> s;
        for (int j = 0; j < w; j++) {
            grid[i][j] = s[j];
        }
    }
    vector<vector<int>> comp(h, vector<int>(w, -1));
    int num_comp = 0;
    vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    vector<vector<pair<int, int>>> cells_comp;
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '0' && comp[i][j] == -1) {
                queue<pair<int, int>> q;
                q.push({i, j});
                comp[i][j] = num_comp;
                vector<pair<int, int>> cells;
                cells.push_back({i, j});
                while (!q.empty()) {
                    auto [x, y] = q.front();
                    q.pop();
                    for (auto [dx, dy] : dirs) {
                        int nx = x + dx, ny = y + dy;
                        if (nx >= 0 && nx < h && ny >= 0 && ny < w && grid[nx][ny] == '0' && comp[nx][ny] == -1) {
                            comp[nx][ny] = num_comp;
                            q.push({nx, ny});
                            cells.push_back({nx, ny});
                        }
                    }
                }
                cells_comp.push_back(cells);
                num_comp++;
            }
        }
    }
    vector<vector<int>> adj_super(num_comp);
    for (int i = 0; i < h; i++) {
        for (int j = 0; j < w; j++) {
            if (grid[i][j] == '0') {
                int c = comp[i][j];
                for (auto [dx, dy] : dirs) {
                    int ni = i + dx, nj = j + dy;
                    if (ni >= 0 && ni < h && nj >= 0 && nj < w && grid[ni][nj] == '0' && comp[ni][nj] != c) {
                        adj_super[c].push_back(comp[ni][nj]);
                    }
                }
            }
        }
    }
    for (int i = 0; i < num_comp; i++) {
        sort(adj_super[i].begin(), adj_super[i].end());
        auto it = unique(adj_super[i].begin(), adj_super[i].end());
        adj_super[i].resize(it - adj_super[i].begin());
    }
    vector<int> super_comp(num_comp, -1);
    int num_super = 0;
    for (int i = 0; i < num_comp; i++) {
        if (super_comp[i] == -1) {
            queue<int> q;
            q.push(i);
            super_comp[i] = num_super;
            while (!q.empty()) {
                int u = q.front();
                q.pop();
                for (int v : adj_super[u]) {
                    if (super_comp[v] == -1) {
                        super_comp[v] = num_super;
                        q.push(v);
                    }
                }
            }
            num_super++;
        }
    }
    vector<vector<pair<int, int>>> cells_super(num_super);
    for (int c = 0; c < num_comp; c++) {
        int sc = super_comp[c];
        for (auto p : cells_comp[c]) {
            cells_super[sc].push_back(p);
        }
    }
    vector<long long> V_SC(num_super, 0);
    for (int sc = 0; sc < num_super; sc++) {
        if (cells_super[sc].empty()) continue;
        pair<int, int> start = cells_super[sc][0];
        vector<vector<char>> visited(h, vector<char>(w, 0));
        queue<pair<int, int>> q;
        q.push(start);
        visited[start.first][start.second] = 1;
        long long flooded = 1;
        while (!q.empty()) {
            auto [x, y] = q.front();
            q.pop();
            for (auto [dx, dy] : dirs) {
                int nx = x + dx, ny = y + dy;
                if (nx >= 0 && nx < h && ny >= 0 && ny < w && !visited[nx][ny]) {
                    if (grid[nx][ny] == '0') {
                        visited[nx][ny] = 1;
                        q.push({nx, ny});
                        flooded++;
                    } else if (grid[nx][ny] == '1') {
                        int cnt = 0;
                        for (auto [ddx, ddy] : dirs) {
                            int nnx = nx + ddx, nny = ny + ddy;
                            if (nnx >= 0 && nnx < h && nny >= 0 && nny < w && visited[nnx][nny]) {
                                cnt++;
                            }
                        }
                        if (cnt >= 2) {
                            visited[nx][ny] = 1;
                            q.push({nx, ny});
                            flooded++;
                        }
                    }
                }
            }
        }
        V_SC[sc] = flooded;
    }
    long long total = 0;
    for (int c = 0; c < num_comp; c++) {
        int sc = super_comp[c];
        total += (long long)cells_comp[c].size() * V_SC[sc];
    }
    cout << total << endl;
    return 0;
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...