제출 #1337148

#제출 시각아이디문제언어결과실행 시간메모리
1337148nxk02102010Flooding (NOI25_flooding)C++20
12 / 100
3095 ms38924 KiB
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define F first
#define S second
#define ID(x,y) ((x-1)*m + (y-1))
const int MAX = 5005;
char a[MAX][MAX];
int n,m;
int p[2500002],sz[2500002],t[2500002],vist[2500002];
int find(int v){
    return v == p[v] ? v : p[v] = find(p[v]);
}
bool unite(int a,int b){
    a = find(a);b = find(b);
    if(a == b) return 0;
    if(sz[a] < sz[b]) swap(a,b);
    p[b] = a;
    sz[a] += sz[b];
    return 1;
}
const int dx[] = {1,-1,0,0},dy[] = {0,0,-1,1};
bool vis[MAX][MAX];
bool checkpos(int i,int j){
    return i >= 1 && i <= n && j >= 1 && j <= m && a[i][j] == '0' && !vis[i][j];
}
void dfs(int i,int j){
    vis[i][j] = 1;
    for(int d = 0;d < 4;d++){
        int x = i + dx[d];
        int y = j + dy[d];
        if(checkpos(x,y)) unite(ID(i,j),ID(x,y)),dfs(x,y);
    }
}
void dfs2(int i,int j,int &s,stack<pair<int,int>> &q){
    s++;
    vist[ID(i,j)] = 1;
    q.push({i,j});
    //cerr<<"took " << i << ' ' << j << '\n';
    if(a[i][j] == '1') t[ID(i,j)] = 2;
    for(int d = 0;d < 4;d++){
        int x = i + dx[d];
        int y = j + dy[d];
        if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '0' && !vist[ID(x,y)]) dfs2(x,y,s,q);
        else if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '1' && t[ID(x,y)] == 1) dfs2(x,y,s,q);
        else if(x >= 1 && x <= n && y >= 1 && y <= m && a[x][y] == '1' && t[ID(x,y)] == 0) {t[ID(x,y)]++;q.push({x,y});}
    }
}
void reserv(stack<pair<int,int>> &q){
    while(!q.empty()){
        auto top = q.top();q.pop();
        int i = top.F;
        int j = top.S;
        vist[ID(i,j)] = 0;
        t[ID(i,j)] = 0;
        //cerr<< "rev " << i << ' ' << j << '\n';
    }
}
void solve(){
    cin >> n >> m;
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++) cin >> a[i][j];
    iota(p,p + n * m + m + 1,0);
    fill(sz,sz + n * m + m + 1,1);
    for(int i = 1;i <= n;i++) for(int j = 1;j <= m;j++){
        if(a[i][j] == '0' && !vis[i][j]){
            dfs(i,j);
        }
    }
    vector<bool> rootvis(n * m + m,0);
    int sum = 0;
    bool ok = 0;
    int COM = 0;
    for(int i = 1;i <= n;i++){
        for(int j = 1;j <= m;j++){
            if(a[i][j] == '0' && !rootvis[find(ID(i,j))]){
                int s = 0;
                stack<pair<int,int>> q;
                //cerr<<"Component: " << ++COM << '\n';
                dfs2(i,j,s,q);
                cerr<< "REV" << '\n';
                reserv(q);
                sum += s * sz[find(ID(i,j))];
                rootvis[find(ID(i,j))] = 1;
                //cerr<< s << ' ' << sz[find(ID(i,j))] << ' ' << s * sz[find(ID(i,j))] << "\n\n";
            }
        }
    }
    cout << sum << '\n';
}
signed main(){
    //freopen("FloodinDL.Inp","r",stdin);
    //freopen("FloodinDL.Out","w",stdout);
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    solve();
}
#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...