Submission #898373

#	Time	Username	Problem	Language	Result	Execution time	Memory
898373		penguin133	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	1 ms	4704 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[9000005], 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;
}

void solve(){
	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 * m; i++)par[i] = i;
	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'){
				merge(conv(i, j), conv(i + 1, j));
				merge(conv(i + 1, j), conv(i + 2, j));
				vert[getr(conv(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'){
				merge(conv(i, j), conv(i, j + 1));
				merge(conv(i, j + 1), conv(i, j + 2));
				hor[getr(conv(i, j))]++;
			}
		}
	}
	int ans = 0;
	for(int i = 1; i <= n * m; i++){
		if(used[getr(i)])continue;
		used[getr(i)] = 1;
		ans += max(hor[getr(i)], vert[getr(i)]);
	}
	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:60:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   60 | main(){
      | ^~~~

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