제출 #650231

#제출 시각아이디문제언어결과실행 시간메모리
650231truc12a2cvpRaspad (COI17_raspad)C++14
100 / 100
534 ms291324 KiB
#include<bits/stdc++.h> using namespace std; typedef long long ll; typedef pair<int, int> II; const int N = 1e5 + 5, logN = 20; const int MOD = 1e9 + 7; const ll INF = 1e9; int n, m, vis[N][55], minx, maxx, comp[N][55], nComp; char a[N][55]; vector<II> vt; inline bool inside(int x, int y){ return x >= 1 && x <= n && y >= 1 && y <= m; } void dfs(int x, int y){ vis[x][y] = true; vt.push_back(II(x, y)); comp[x][y] = nComp; minx = min(minx, x); maxx = max(maxx, x); for(int nx = x - 1; nx <= x + 1; nx ++){ for(int ny = y - 1; ny <= y + 1; ny ++){ if(inside(nx, ny) && !vis[nx][ny] && a[nx][ny] == '0') dfs(nx, ny); } } } int main(){ //freopen("datpat.inp", "r", stdin); //freopen("datpat.out", "w", stdout); ios_base::sync_with_stdio(false); cin.tie(0); cin >> n >> m; for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++) cin >> a[i][j]; } ll ans = 0; for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ if(a[i][j] == '1'){ ans += i * 1ll * (n - i + 1); if(a[i - 1][j] == '1') ans -= (i - 1) * 1ll * (n - i + 1); if(a[i][j - 1] == '1') ans -= i * 1ll * (n - i + 1); if(a[i - 1][j] == a[i][j - 1] && a[i - 1][j] == '1' && a[i - 1][j - 1] == '1') ans += (i - 1) * 1ll * (n - i + 1); } } } for(int i = 1; i <= n; i ++){ for(int j = 1; j <= m; j ++){ if(!vis[i][j] && a[i][j] == '0'){ minx = INF; maxx = -INF; nComp ++; vt.clear(); dfs(i, j); bool check = true; for(auto xy : vt){ int x = xy.first, y = xy.second; for(int nx = x - 1; nx <= x + 1; nx ++){ for(int ny = y - 1; ny <= y + 1; ny ++) check &= (comp[nx][ny] == nComp || a[nx][ny] == '1'); } } if(check) ans += (minx - 1) * 1ll * (n - maxx); } } } cout << ans << endl; return 0; } /* 5 7 0100010 0111110 0101001 1111011 0100100 */
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...