Submission #712320

#	Time	Username	Problem	Language	Result	Execution time	Memory
712320		dozer	Dango Maker (JOI18_dango_maker)	C++14	13 / 100	1 ms	340 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
#define sp " "
#define endl "\n";
#define fastio() cin.tie(0), ios_base::sync_with_stdio(0)
#define pb push_back
#define pii pair<int, int>
#define st first
#define nd second
#define N 3005

const int modulo = 1e9 + 7;

int arr[N][N], root[N * N], done[N][N];
pii sz[N];
set<int> roots;

int find(int node)
{
	if (root[node] == node) return node;
	return root[node] = find(root[node]); 
}


void uni(int a, int b)
{
	a = find(a), b = find(b);
	if (sz[a].st + sz[a].nd < sz[b].st + sz[b].nd) swap(a, b);
	if (a == b) return;
	root[b] = a;
	roots.erase(b);
	sz[a].st += sz[b].st, sz[a].nd += sz[b].nd;
}

int32_t main()
{
	fastio();

	map<char, int> val;
	val['R'] = 1, val['G'] = 2, val['W'] = 3;

	int n, m;
	cin>>n>>m;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			char tmp;
			cin>>tmp;
			arr[i][j] = val[tmp];
		}
	}
	for (int i = 1; i <= n; i++) for (int j = 1; j <= m; j++) done[i][j] = (i - 1) * m + j;
	for (int i = 1; i <= n * m; i++) root[i] = i, roots.insert(i);

	int ans = 0;
	for (int i = 1; i <= n; i++)
	{
		for (int j = 1; j <= m; j++)
		{
			int val = 0, f = 1;
			for (int k = i; k <= i + 2; k++)
			{
				val += arr[k][j] * f;
				f *= 10;
			}
			if (val == 321)
			{
				//cout<<"v "<<i<<sp<<j<<endl;
				sz[find(done[i][j])].st++;
				for (int k = i + 1; k <= i + 2; k++)
					uni(done[i][j], done[k][j]);
			}


			val = 0, f = 1;
			for (int k = j; k <= j + 2; k++)
			{
				val += arr[i][k] * f;
				f *= 10;
			}
			if (val == 321)
			{
				//cout<<"> "<<i<<sp<<j<<endl;
				sz[find(done[i][j])].nd++;
				for (int k = j + 1; k <= j + 2; k++)
					uni(done[i][j], done[i][k]);
			}
		}
	}

	for (auto i : roots)
	{
		ans += max(sz[i].st, sz[i].nd);
	}
	cout<<ans<<endl;
	cerr << "time taken : " << (float)clock() / CLOCKS_PER_SEC << " seconds\n";
}

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