Submission #20525840


Source Code Expand

Copy
#include <cassert>
#include <cmath>
#include <cstdint>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
#include <bitset>
#include <complex>
#include <deque>
#include <functional>
#include <iostream>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <sstream>
#include <string>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>

using namespace std;

using Int = long long;

template <class T1, class T2> ostream &operator<<(ostream &os, const pair<T1, T2> &a) { return os << "(" << a.first << ", " << a.second << ")"; };
template <class T> void pv(T a, T b) { for (T i = a; i != b; ++i) cerr << *i << " "; cerr << endl; }
template <class T> bool chmin(T &t, const T &f) { if (t > f) { t = f; return true; } return false; }
template <class T> bool chmax(T &t, const T &f) { if (t < f) { t = f; return true; } return false; }


namespace MF {
	const int LIM_N = 1'000'010;
	const int LIM_M = 1'000'010;
	typedef int wint;
	const wint wEPS = 0;
	const wint wINF = 1001001001;
	int n, m, ptr[LIM_N], nxt[LIM_M * 2], zu[LIM_M * 2];
	wint capa[LIM_M * 2], tof;
	int lev[LIM_N], see[LIM_N], que[LIM_N], *qb, *qe;
	void init(int _n) {
		n = _n; m = 0; fill(ptr, ptr + n, -1);
	}
	void ae(int u, int v, wint w0, wint w1 = 0) {
		nxt[m] = ptr[u]; ptr[u] = m; zu[m] = v; capa[m] = w0; ++m;
		nxt[m] = ptr[v]; ptr[v] = m; zu[m] = u; capa[m] = w1; ++m;
	}
	wint augment(int src, int ink, wint flo) {
		if (src == ink) return flo;
		for (int &i = see[src]; ~i; i = nxt[i]) if (capa[i] > wEPS && lev[src] < lev[zu[i]]) {
			const wint f = augment(zu[i], ink, min(flo, capa[i]));
			if (f > wEPS) {
				capa[i] -= f; capa[i ^ 1] += f; return f;
			}
		}
		return 0;
	}
	bool solve(int src, int ink, wint flo = wINF) {
		for (tof = 0; tof + wEPS < flo; ) {
			qb = qe = que; fill(lev, lev + n, -1);
			for (lev[*qe++ = src] = 0, see[src] = ptr[src]; qb != qe; ) {
				const int u = *qb++;
				for (int i = ptr[u]; ~i; i = nxt[i]) if (capa[i] > wEPS) {
					const int v = zu[i];
					if (lev[v] == -1) {
						lev[*qe++ = v] = lev[u] + 1; see[v] = ptr[v];
						if (v == ink) goto au;
					}
				}
			}
			return false;
		au:	for (wint f; (f = augment(src, ink, flo - tof)) > wEPS; tof += f);
		}
		return true;
	}
}


int N;
char A[110][110];

int main() {
  for (; ~scanf("%d", &N); ) {
    for (int x = 0; x < N; ++x) {
      scanf("%s", A[x]);
    }
    
    MF::init(2 + N * N);
    auto id = [&](int x, int y) {
      return 2 + x * N + y;
    };
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
      if ((x + y) % 2 == 0) {
        if (A[x][y] == 'B') {
          MF::ae(0, id(x, y), MF::wINF);
        } else if (A[x][y] == 'W') {
          MF::ae(id(x, y), 1, MF::wINF);
        }
      } else {
        if (A[x][y] == 'B') {
          MF::ae(id(x, y), 1, MF::wINF);
        } else if (A[x][y] == 'W') {
          MF::ae(0, id(x, y), MF::wINF);
        }
      }
    }
    for (int x = 0; x < N; ++x) for (int y = 0; y < N; ++y) {
      if (x > 0) {
        MF::ae(id(x - 1, y), id(x, y), 1, 1);
      }
      if (y > 0) {
        MF::ae(id(x, y - 1), id(x, y), 1, 1);
      }
    }
    MF::solve(0, 1);
    const int ans = 2 * N * (N - 1) - MF::tof;
    printf("%d\n", ans);
  }
  return 0;
}

Submission Info

Submission Time
Task F - Zebraness
User hos_lyric
Language C++ (GCC 9.2.1)
Score 600
Code Size 3412 Byte
Status AC
Exec Time 21 ms
Memory 4608 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:87:12: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   87 |       scanf("%s", A[x]);
      |       ~~~~~^~~~~~~~~~~~

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 600 / 600
Status
AC × 3
AC × 41
Set Name Test Cases
Sample 01_sample.txt, 02_sample.txt, 03_sample.txt
All 01_sample.txt, 02_sample.txt, 03_sample.txt, 04_hand.txt, 05_hand.txt, 06_small.txt, 07_small.txt, 08_small.txt, 09_small.txt, 10_small.txt, 11_small.txt, 12_small.txt, 13_small.txt, 14_small.txt, 15_small.txt, 16_small.txt, 17_small.txt, 18_large.txt, 19_large.txt, 20_large.txt, 21_large.txt, 22_large.txt, 23_large.txt, 24_large.txt, 25_large.txt, 26_large.txt, 27_large.txt, 28_max.txt, 29_max.txt, 30_max.txt, 31_max.txt, 32_max.txt, 33_max.txt, 34_max.txt, 35_max.txt, 36_max.txt, 37_max.txt, 38_max.txt, 39_max.txt, 40_max.txt, 41_max.txt
Case Name Status Exec Time Memory
01_sample.txt AC 10 ms 3756 KB
02_sample.txt AC 2 ms 3624 KB
03_sample.txt AC 2 ms 3748 KB
04_hand.txt AC 3 ms 3744 KB
05_hand.txt AC 2 ms 3752 KB
06_small.txt AC 2 ms 3764 KB
07_small.txt AC 2 ms 3636 KB
08_small.txt AC 2 ms 3764 KB
09_small.txt AC 2 ms 3764 KB
10_small.txt AC 2 ms 3640 KB
11_small.txt AC 3 ms 3756 KB
12_small.txt AC 2 ms 3792 KB
13_small.txt AC 2 ms 3860 KB
14_small.txt AC 2 ms 3752 KB
15_small.txt AC 2 ms 3620 KB
16_small.txt AC 2 ms 3760 KB
17_small.txt AC 2 ms 3672 KB
18_large.txt AC 5 ms 4124 KB
19_large.txt AC 3 ms 4144 KB
20_large.txt AC 2 ms 3716 KB
21_large.txt AC 4 ms 4168 KB
22_large.txt AC 6 ms 3952 KB
23_large.txt AC 11 ms 4320 KB
24_large.txt AC 11 ms 4428 KB
25_large.txt AC 9 ms 4272 KB
26_large.txt AC 18 ms 4328 KB
27_large.txt AC 4 ms 4552 KB
28_max.txt AC 11 ms 4564 KB
29_max.txt AC 9 ms 4432 KB
30_max.txt AC 16 ms 4360 KB
31_max.txt AC 5 ms 4608 KB
32_max.txt AC 4 ms 4520 KB
33_max.txt AC 2 ms 4336 KB
34_max.txt AC 4 ms 4604 KB
35_max.txt AC 11 ms 4596 KB
36_max.txt AC 21 ms 4324 KB
37_max.txt AC 16 ms 4536 KB
38_max.txt AC 17 ms 4500 KB
39_max.txt AC 6 ms 4436 KB
40_max.txt AC 6 ms 4516 KB
41_max.txt AC 7 ms 4560 KB