oj.uz

Submission #41107

# Submission time Handle Problem Language Result Execution time Memory
41107 2018-02-12T19:10:32 Z abeker Dango Maker (JOI18_dango_maker) C++14
0 / 100
 62 ms 71024 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 3e3 + 5;
const int MAXS = 3e6 + 5;
const int INF = 0x3f3f3f3f;

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

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);
}

void compress(int &ref) {
	if (ref)
		ref = lower_bound(all.begin(), all.end(), ref) - all.begin() + 1;
}

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 (auto it : lft)
		all.push_back(it);
		
	for (auto it : rig)
		all.push_back(it);
	
	sort(all.begin(), all.end());
	
	for (int i = 0; i < N; i++)
		for (int j = 0; j < M; j++) {
			compress(hor[i][j]);
			compress(ver[i][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

dango_maker.cpp: In function 'void load()':
dango_maker.cpp:16: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:18:22: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", mat[i]);
                      ^

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70904 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 61 ms 70952 KB Output is correct
4 Correct 62 ms 70952 KB Output is correct
5 Correct 60 ms 71024 KB Output is correct
6 Incorrect 58 ms 71024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70904 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 61 ms 70952 KB Output is correct
4 Correct 62 ms 70952 KB Output is correct
5 Correct 60 ms 71024 KB Output is correct
6 Incorrect 58 ms 71024 KB Output isn't correct
7 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 61 ms 70904 KB Output is correct
2 Correct 58 ms 70904 KB Output is correct
3 Correct 61 ms 70952 KB Output is correct
4 Correct 62 ms 70952 KB Output is correct
5 Correct 60 ms 71024 KB Output is correct
6 Incorrect 58 ms 71024 KB Output isn't correct
7 Halted 0 ms 0 KB -