Submission #1319732

#TimeUsernameProblemLanguageResultExecution timeMemory
1319732byunjaewooRaspad (COI17_raspad)C++20
100 / 100
1112 ms784736 KiB
#include <bits/stdc++.h>
#define int long long
using namespace std;

const int N=100010, M=55;
int n, m, t, ans, a[N][M], chk[4][N][M];
bool visited[N][M];
array<int, 3> par[4][N][M];
int dx[4]={-1, 0, 1, 0}, dy[4]={0, 1, 0, -1};

void f(int i, int j, int td) {
    chk[td][i][j]=1;
    for(int e=1; e<=4; e++) {
        int d=(td+2+e)%4;
        int ii=i+dx[d], jj=j+dy[d];
        if(ii<1 || ii>n || jj<1 || jj>m || !a[ii][jj]) continue;
        if(!chk[d][ii][jj]) par[d][ii][jj]={td, i, j}, f(ii, jj, d);
        else if(chk[d][ii][jj]==1) {
            array<int, 3> curr={td, i, j};
            int mn=i, mx=i;
            while(curr[0]!=d || curr[1]!=ii || curr[2]!=jj) {
                curr=par[curr[0]][curr[1]][curr[2]];
                mn=min(mn, curr[1]), mx=max(mx, curr[1]);
            }
            ans+=mn*(n-mx+1);
        }
        break;
    }
    chk[td][i][j]=2;
}

signed main() {
    ios_base::sync_with_stdio(0); cin.tie(0);
    cin>>n>>m;
    for(int i=1; i<=n; i++) {
        string s; cin>>s;
        for(int j=1; j<=m; j++) a[i][j]=s[j-1]-'0';
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) ans+=a[i][j]*i*(n-i+1);
    for(int i=1; i<=n; i++) for(int j=1; j<m; j++) if(a[i][j] && a[i][j+1]) ans-=i*(n-i+1);
    for(int i=1; i<n; i++) for(int j=1; j<=m; j++) if(a[i][j] && a[i+1][j]) ans-=i*(n-i);
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(a[i][j]) for(int d=0; d<4; d++) {
        int ii=i+dx[d], jj=j+dy[d];
        if(ii<1 || ii>n || jj<1 || jj>m || !a[ii][jj] || chk[d][ii][jj]) continue;
        f(ii, jj, d);
    }
    for(int i=1; i<=n; i++) for(int j=1; j<=m; j++) if(a[i][j] && !visited[i][j]) {
        int mn=i, mx=i, cnt=0;
        queue<pair<int, int>> que; que.push({i, j});
        visited[i][j]=true;
        while(!que.empty()) {
            auto [i, j]=que.front(); que.pop();
            mn=min(mn, i), mx=max(mx, i), visited[i][j]=true, ++cnt;
            for(int d=0; d<4; d++) {
                int ii=i+dx[d], jj=j+dy[d];
                if(ii<1 || ii>n || jj<1 || jj>m || !a[ii][jj] || visited[ii][jj]) continue;
                visited[ii][jj]=true, que.push({ii, jj});
            }
        }
        ans-=(cnt>1)*mn*(n-mx+1);
    }
    cout<<ans;
    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...