Submission #572411

#	Time	Username	Problem	Language	Result	Execution time	Memory
572411		ImperialALEN	Dijamant (COCI22_dijamant)	C++17	70 / 70	327 ms	240820 KiB

Main

//#pragma GCC optomize ("Ofast")
//#pragma GCC optomize ("unroll-loops")
//#pragma GCC target ("avx,avx2,fma")
#include <bits/stdc++.h>
  
#define F first
#define S second 
#define ll long long
#define all(x) (x.begin(), x.end());
#define uint unsigned int
#define pb push_back
 
using namespace std;
  
const ll N = 2e5+1, INF = 1e18 , inf = 1e9 , mod = 1e9+7;

int n, m, cnt = 0, mn = inf, mx = -inf, mxsum, mnsum;
char a[2002][2002];
bool used[2002][2002];
int di[4]{-1, 0, 1, 0};
int dj[4]{0, -1, 0, 1};
bool ok = 0;

void dfs(int vi, int vj){
	used[vi][vj] = 1; 
	cnt++;
	mx = max(mx, vi-vj);
	mn = min(mn, vi-vj);
	mxsum = max(mxsum, vi+vj);
	mnsum = min(mnsum, vi+vj);
	for(int i = 0; i < 4; i++){
		int toi = vi+di[i], toj = vj+dj[i];
		if(toi >= 1 && toi <= n && toj >= 1 && toj <= m){
			if(!used[toi][toj] && a[toi][toj] == '.'){
				dfs(toi, toj);
			}
		}
		else{
			ok = 1;
		}
	}
}

int main(){
//  	freopen("points.in", "r", stdin);
//  	freopen("points.out", "w", stdout);
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin >> n >> m;
    for(int i = 1; i <= n; i++){
    	for(int j = 1; j <= m; j++){
    		cin >> a[i][j];
		}
	}
	int ans = 0;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(used[i][j] || a[i][j] == '#') continue;
			else{
				cnt = 0;
				mx = -inf;
				mn = inf;
				mxsum = -inf;
				mnsum = inf;
				ok = 0;
				dfs(i, j);
 				if(mxsum-mnsum == mx-mn && (mxsum-mnsum)%2 == 0 && !ok){
					int q = (mxsum-mnsum)/2+1;
					if(2*q*q-2*q+1 == cnt) ans++;
				}
			}
		}
	}
	cout  << ans;
	return 0;
}

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