Submission #483947

#	Time	Username	Problem	Language	Result	Execution time	Memory
483947		ymm	Dango Maker (JOI18_dango_maker)	C++17	100 / 100	1255 ms	137148 KiB

dango_maker

///
///   You fell for it, fool!
///   Thunder Cross Split Attack!
///

#include <bits/stdc++.h>
#define Loop(x,l,r) for(ll x = ll(l); x < ll(r); ++x)
typedef long long ll;
typedef std::pair<int,int> pii;
using namespace std;

const int N = 3009;
int ch, cv;
char a[N][N];
int n, m;
int mch[N*N];
pair<int,int> par[N*N];
bitset<N*N> vis;
vector<int> dard;

bool gdh(int i, int j){return 0 <= i && i < n && 0 <= j && j+3 <= m && a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W';}
bool gdv(int i, int j){return 0 <= i && i+2 <= n && 0 <= j && j < m && a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W';}

bool bfs(int s)
{
	par[s] = {-1, -1};
	vector<int> q;
	q.push_back(s); vis[s] = 1;
	for(int i = 0; i < q.size(); ++i)
	{
		auto v = q[i];
		Loop(i,0,3)
		{
			if(!gdv(v/N-i,v%N+i)) continue;
			int u = v-i*(N-1);
			if(mch[u] == -1){
				while(v != -1){
					mch[u] = v;
					u = par[v].second;
					v = par[v].first;
				}
				for(int z : q) vis[z] = 0;
				return 1;
			}
			if(vis[mch[u]]) continue;
			q.push_back(mch[u]);
			vis[mch[u]] = 1;
			par[mch[u]] = {v, u};
		}
	}
	return 0;
}

int main()
{
	ios::sync_with_stdio(false); cin.tie(0);
	cin >> n >> m;
	Loop(i,0,n) cin >> a[i];
	int ans = 0;
	Loop(i,0,n) Loop(j,0,m) {
		if(gdh(i,j)) dard.push_back(N*i+j);
		if(gdv(i,j)) ++ans;
	}
	ans += dard.size();
	srand(time(0));
	random_shuffle(dard.begin(), dard.end());
	memset(mch, -1, sizeof mch);
	for(int v : dard)
	{
		ans -= bfs(v);
	}
	cout << ans << '\n';
}

Compilation message (stderr)

dango_maker.cpp: In function 'bool bfs(int)':
dango_maker.cpp:29:19: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   29 |  for(int i = 0; i < q.size(); ++i)
      |                 ~~^~~~~~~~~~

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