Submission #1319730

#	Time	Username	Problem	Language	Result	Execution time	Memory
1319730		byunjaewoo	Raspad (COI17_raspad)	C++20	61 / 100	1076 ms	1114112 KiB

raspad

#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) {
            vector<array<int, 3>> tmp;
            int mn=i, mx=i;
            tmp.push_back({td, i, j});
            while(tmp.back()[0]!=d || tmp.back()[1]!=ii || tmp.back()[2]!=jj) {
                tmp.push_back(par[tmp.back()[0]][tmp.back()[1]][tmp.back()[2]]);
                mn=min(mn, tmp.back()[1]), mx=max(mx, tmp.back()[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;
}

• Subtask 1: 9 / 9
• Subtask 2: 17 / 17
• Subtask 3: 35 / 35
• Subtask 4: 0 / 39