Submission #1262189

#	Time	Username	Problem	Language	Result	Execution time	Memory
1262189		dhuyyyy	Dijamant (COCI22_dijamant)	C++20	70 / 70	231 ms	237460 KiB

Main

#include <bits/stdc++.h>
#define fi first
#define se second
#define int long long
using namespace std;

using ll = long long;
using ii = pair<int,int>;
using pii = pair<int,ii>;
using aa = array<int,4>;

const int N = 2005;
const int INF = 1e9;
const int MOD = 998244353;

int n,m,cnt,res = 0;
ii mx,mn;
int dx[4] = {1,0,-1,0};
int dy[4] = {0,1,0,-1};
bool vis[N][N];
char a[N][N];

bool ok(int i,int j){
    return i >= 1 && i <= n && j >= 1 && j <= m && a[i][j] == '.' && !vis[i][j];
}
bool ok2(int i,int j){
    return i > 1 && i < n && j > 1 && j < m;
}
void dfs(int i,int j){
    if (!ok2(i,j)) cnt = 1e9+5;
    vis[i][j] = 1;
    cnt++;
    mx.fi = max(mx.fi,i+j);
    mn.fi = min(mn.fi,i+j);
    mx.se = max(mx.se,i-j);
    mn.se = min(mn.se,i-j);
    for (int k = 0; k < 4; k++){
        int x = i + dx[k];
        int y = j + dy[k];
        if (ok(x,y)) dfs(x,y);
    }
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);
    cin >> n >> m;
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            cin >> a[i][j];
        }
    }
    for (int i = 1; i <= n; i++){
        for (int j = 1; j <= m; j++){
            if (a[i][j] == '.' && !vis[i][j]){
                cnt = 0;
                mx = {-1e9,-1e9};
                mn = {1e9,1e9};
                dfs(i,j);
                if (mx.fi - mn.fi != mx.se - mn.se || (mx.fi - mn.fi) % 2 != 0) continue;
                int tmp = (mx.fi - mn.fi) / 2 + 1;
                res += (tmp * tmp + (tmp - 1) * (tmp - 1) == cnt);
            }
        }
    }
    cout << res;
    return 0;
}

• Subtask 1: 20 / 20
• Subtask 2: 50 / 50