제출 #234978

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
234978		Atalasion	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	124 ms	213240 KiB

dango_maker

//khodaya khodet komak kon
#include <bits/stdc++.h>

#define F first
#define S second
#define pb push_back
#define all(x) x.begin(), x.end()
#pragma GCC optimize ("Ofast")
#pragma GCC optimize("unroll-loops")
#pragma GCC optimize ("-O2")


using namespace std;

typedef long long ll;
typedef pair<int, int> pii;
typedef vector<int> vi;

const int N = 3000 + 10;
const ll MOD = 1000000000 + 7;
const ll INF = 1000000010;
const ll LOG = 25;

int n, m, mark[N][N], cnt;
char a[N][N];
vector<pii> G[N][N];

void DFS(pii v){
	cnt++;
	mark[v.F][v.S] = 1;
	for (auto u:G[v.F][v.S]){
		if (mark[u.F][u.S] == 0) DFS(u);
	}
}

int32_t main(){
	ios::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];
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m - 2; j++){
		if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') G[i][j].pb({i, j + 2}), G[i][j + 2].pb({i, j});
	}
	for (int i = 1; i <= n - 2; i++){
		for (int j = 1; j <= m; j++){
			if (a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') G[i][j].pb({i + 2, j}), G[i + 2][j].pb({i, j});
		}
	}
	int ans = 0;
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++){
		if (mark[i][j] == 0){
			cnt = 0;
			DFS({i, j});
			ans += cnt / 2;
		}
	}
	cout << ans;








	return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67