Submission #58734

#	Time	Username	Problem	Language	Result	Execution time	Memory
58734		YaDon4ick	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	1681 ms	263168 KiB

dango_maker

//By Don4ick
//#define _GLIBCXX_DEBUG

#include <bits/stdc++.h>

typedef long long ll;
typedef long double ld;
typedef unsigned int ui;

#define forn(i, n) for (int i = 1; i <= n; i++)
#define pb push_back
#define all(x) x.begin(), x.end()
#define y1 qwer1234

const double PI = acos(-1.0);
const int DIR = 4;
const int X[] = {1, 0, -1, 0};
const int Y[] = {0, 1, 0, -1};

const int N = 3005;
const int M = N * N * 2;

using namespace std;

int n, m, was[M], cnt0, cnt1;	
vector < int > g[M];
string s[N];

void addEdge(int x1, int y1, int x2, int y2)
{
	int v = x1 * m + y1, u = x2 * m + y2 + n * m;
	g[v].pb(u), g[u].pb(v);
}

void dfs(int v)
{
	if (was[v] == 0)
		cnt0++;
	else
		cnt1++;
	for (auto to : g[v])
	{
		if (was[to] != -1)
			continue;
		was[to] = was[v] ^ 1;
		dfs(to);
	}
}

int main()
{
	ios_base::sync_with_stdio(false);
	cin.tie(NULL);
	cout.tie(NULL);

	//freopen(".in", "r", stdin);
	//freopen(".out", "w", stdout);

	//~read
	cin >> n >> m;
	for (int i = 0; i < n; i++)
	{
		cin >> s[i];
	}
	//~build_graph
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m - 2; j++)
		{
			if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W')
			{
				if (i < n - 2 && s[i + 1][j] == 'G' && s[i + 2][j] == 'W')
					addEdge(i, j, i, j);
				if (i < n - 1 && i > 0 && s[i - 1][j + 1] == 'R' && s[i + 1][j + 1] == 'W')
					addEdge(i, j, i - 1, j + 1);
				if (i > 1 && s[i - 2][j + 2] == 'R' && s[i - 1][j + 2] == 'G')
					addEdge(i, j, i - 2, j + 2); 
			}
		}
	}
	//~solve
	memset(was, -1, sizeof(was));
	int ans = 0;
	for (int i = 0; i < n; i++)
	{
		for (int j = 0; j < m - 2; j++)
		{
			int v = i * m + j;
			if (s[i][j] == 'R' && s[i][j + 1] == 'G' && s[i][j + 2] == 'W' && was[v] == -1)
			{
				cnt0 = cnt1 = was[v] = 0;
				dfs(v);
				ans += max(cnt1, cnt0);
			}
		}
	}
	for (int i = 0; i < n - 2; i++)
	{
		for (int j = 0; j < m; j++)
		{
			int v = i * m + j + n * m;
			if (s[i][j] == 'R' && s[i + 1][j] == 'G' && s[i + 2][j] == 'W' && was[v] == -1)
			{
				cnt0 = cnt1 = was[v] = 0;
				dfs(v);
				ans += max(cnt1, cnt0);
			}
		}
	}
	cout << ans << endl;

	return 0;
}

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