Submission #898450

#	Time	Username	Problem	Language	Result	Execution time	Memory
898450		penguin133	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	4456 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;

//#define int long long
#define pi pair<int, int>
#define pii pair<int, pi>
#define fi first
#define se second
#ifdef _WIN32
#define getchar_unlocked _getchar_nolock
#endif
mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());

int par[9000005], hor[9000005], vert[9000005], used[3005][3005], n, m;
char A[3005][3005];
 
int getr(int x){return par[x] == x ? x : par[x] = getr(par[x]);}
void merge(int a, int b){
	a = getr(a), b = getr(b);
	if(a == b)return;
	par[b] = a;
	hor[a] += hor[b];
	vert[a] += vert[b];
}

inline int conv(int x, int y){
	return (x - 1) * m + y;
}

int massiveskewer(int x, int y){
	if(A[x][y] == 'G')return 0;
	if(A[x][y] == 'R'){
		if(x + 4 > n || y <= 2)return 0;
		if(A[x+1][y] != 'G')return 0;
		if(A[x+2][y] != 'W')return 0;
		if(A[x+1][y-1] != 'R')return 0;
		if(A[x+2][y-1] != 'G')return 0;
		if(A[x+3][y-1] != 'W')return 0;
		if(A[x+2][y-2] != 'R')return 0;
		if(A[x+3][y-2] != 'G')return 0;
		if(A[x+4][y-2] != 'W')return 0;
		int tmp = 3;
		for(int i = y; i >= y - 2; i--){
			bool f = 1;
			for(int j = x + (y - i); j <= x + (y - i) + 2; j++){
				if(used[j][i])f = 0;
			}
			if(!f)tmp--;
			else for(int j = x + (y - i); j <= x + (y - i) + 2; j++){
				used[j][i] = 1;
			}
		}
		//cout << x << ' ' << y << ' ' << tmp << '\n';
		return tmp;
	}
	if(x + 2 > n || y <= 4)return 0;
	if(A[x][y-1] != 'G')return 0;
	if(A[x][y-2] != 'R')return 0;
	if(A[x+1][y-1] != 'W')return 0;
	if(A[x+1][y-2] != 'G')return 0;
	if(A[x+1][y-3] != 'R')return 0;
	if(A[x+2][y-2] != 'W')return 0;
	if(A[x+2][y-3] != 'G')return 0;
	if(A[x+2][y-4] != 'R')return 0;
	int tmp = 3;
	for(int i = x; i <= x + 2; i++){
		bool f = 1;
		for(int j = y - (i - x); j >= y - (i - x) - 2; j--){
			if(used[i][j])f = 0;
		}
		if(!f)tmp--;
		else for(int j = y - (i - x); j >= y - (i - x) - 2; j--){
			used[i][j] = 1;
		}
	}
	//cout << x << ' ' << y << ' ' << tmp << '\n';
	return tmp;
}

inline bool check(int x, int y){
	if(A[x][y] != 'R')return 0;
	if(used[x][y])return 0;
	if(x + 2 <= n && !used[x+1][y] && !used[x+2][y] && A[x+1][y] == 'G' && A[x+2][y] == 'W'){
		used[x][y] = used[x+1][y] = used[x+2][y] = 1;
		merge(conv(x, y), conv(x+1, y));
		merge(conv(x+1, y), conv(x+2, y));
		vert[getr(conv(x, y))]++;
	}
	if(y + 2 <= n && !used[x][y+1] && !used[x][y+2] && A[x][y+1] == 'G' && A[x][y+2] == 'W'){
		used[x][y] = used[x][y+1] = used[x][y+2] = 1;
		merge(conv(x, y), conv(x, y+1));
		merge(conv(x, y+1), conv(x, y+2));
		hor[getr(conv(x, y))]++;
	}
	return 0;
}

void solve(){
	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 = m; j >= 1; j--){
			ans += massiveskewer(i, j);
		}
	}
	for(int i = 1; i <= n * m; i++)par[i] = i;
	for(int i = 1; i <= n; i++){
		for(int j = 1; j <= m; j++){
			if(check(i, j))ans = ans;
		}
	}
	for(int i = 1; i <= n * m; i++){
		ans += max(hor[getr(i)], vert[getr(i)]);
		hor[getr(i)] = vert[getr(i)] = 0;
	}
	cout << ans;
}

main(){
	ios::sync_with_stdio(0);cin.tie(0);
	int tc = 1;
	//cin >> tc;
	for(int tc1=1;tc1<=tc;tc1++){
		// cout << "Case #" << tc1 << ": ";
		solve();
	}
}

Compilation message (stderr)

dango_maker.cpp:120:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
  120 | main(){
      | ^~~~

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