Submission #41104

#	Time	Username	Problem	Language	Result	Execution time	Memory
41104		abeker	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	45 ms	50108 KiB

dango_maker

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

const int MAXN = 1e3 + 5;
const int INF = 0x3f3f3f3f;

int N, M;
char mat[MAXN][MAXN];
vector <int> E[MAXN * MAXN];
int match[MAXN * MAXN], dist[MAXN * MAXN];
int hor[MAXN][MAXN], ver[MAXN][MAXN];
vector <int> lft, rig;

void load() {
	scanf("%d%d", &N, &M);
	for (int i = 0; i < N; i++)
		scanf("%s", mat[i]);
}

bool bfs() {
  queue <int> Q;
  for (auto it : lft)
    if (!match[it]) {
      dist[it] = 0;
      Q.push(it);
    }
    else 
			dist[it] = INF;
  
  dist[0] = INF;
  while (!Q.empty()) {
    int x = Q.front(); 
		Q.pop();
    if (!x)
    	continue;
    for (auto it : E[x]) 
      if (dist[match[it]] == INF) {
        dist[match[it]] = dist[x] + 1;
        Q.push(match[it]);
      }
  }
  
  return dist[0] != INF;
}

bool dfs(int x) {
  if (!x)
  	return true;
  for (auto it : E[x]) 
    if (dist[match[it]] == dist[x] + 1 && dfs(match[it])) {
      match[it] = x;
      match[x] = it;
      return true;
    }
  dist[x] = INF;
  return false;
}

int hopcroft_karp() {
  int matching = 0;
  while (bfs())
    for (auto it : lft)
      matching += !match[it] && dfs(it);
  return matching;
}

int get(int x, int y) {
	return M * x + y + 1;
}

void check_hor(int x, int y) {
	if (y > M - 3)
		return;
	for (int i = 0; i < 3; i++)
		if (mat[x][y + i] != "RGW"[i])
			return;
	lft.push_back(get(x, y));
	for (int i = 0; i < 3; i++)
		hor[x][y + i] = get(x, y);
}

void check_ver(int x, int y) {
	if (x > N - 3)
		return;
	for (int i = 0; i < 3; i++)
		if (mat[x + i][y] != "RGW"[i])
			return;
	rig.push_back(get(x, y));
	for (int i = 0; i < 3; i++)
		ver[x + i][y] = get(x, y);
}

int solve() {
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			check_hor(i, j);
			check_ver(i, j);
		}
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++)
			if (hor[i][j] && ver[i][j]) 
				E[hor[i][j]].push_back(ver[i][j]);
	
	return lft.size() + rig.size() - hopcroft_karp();
}

int main() {
	load();
	printf("%d\n", solve());
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'void load()':
dango_maker.cpp:15:23: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf("%d%d", &N, &M);
                       ^
dango_maker.cpp:17:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", mat[i]);
                      ^

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