Submission #682089

#	Time	Username	Problem	Language	Result	Execution time	Memory
682089		ethening	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	15 ms	35668 KiB

dango_maker

#include "bits/stdc++.h"
using namespace std;
using ll = long long;

// RGW

template<class T>
struct dinic {
  static constexpr T INF = numeric_limits<T>::max();
  struct edge {
    int v, r; T c;
    edge(int _v, int _r, T _c) : v{_v}, r{_r}, c{_c} {}
  };
  int n, s, t;
  vector<vector<edge>> G;
  vector<int> d, arc;
  dinic(int _n, int _s, int _t) : n{_n}, s{_s}, t{_t}, G(_n) {}

  void add_edge(int u, int v, T c) {
    G[u].emplace_back(v, (int)G[v].size(), c);
    G[v].emplace_back(u, (int)G[u].size() - 1, 0);
  }
  int bfs() {
    d.assign(n, 0), arc.assign(n, 0);
    queue<int> q;
    d[s] = 1, q.emplace(s);
    while (!q.empty()) {
      int u = q.front();
      q.pop();
      for (auto [v, r, c] : G[u]) {
        if (!d[v] && c) {
          d[v] = d[u] + 1;
          if (v == t) return 1;
          q.emplace(v);
        }
      }
    }
    return d[t];
  }
  T dfs(int u, T f) {
    if (u == t) return f;
    T sum = 0;
    for (int& i = arc[u]; i < (int)G[u].size(); ++i) {
      auto& [v, r, c] = G[u][i];
      if (d[v] == d[u] + 1 && c) {
        T res = dfs(v, min(f, c));
        if (res) {
          c -= res, G[v][r].c += res;
          sum += res, f -= res;
          if (!f) return sum;
        } else {
          d[v] = 0;
        }
      }
    }
    return sum;
  }
  T max_flow() {
    T sum = 0;
    while (bfs()) {
      while (T res = dfs(s, INF)) {
        sum += res;
      }
    }
    return sum;
  }
};


// bool dfs(int cur) {
// 	for (int nxt : va[cur]) {
// 		if (!visitb[nxt]) {
// 			visitb[nxt] = true;
// 			clrS.push(nxt);
// 			if (mb[nxt] == 0 || dfs(mb[nxt])) {
// 				ma[cur] = nxt;
// 				mb[nxt] = cur;
// 				return true;
// 			}
// 		}
// 	}
// 	return false;
// }


// int bipartite_matching() {
// 	memset(ma, -1, sizeof(ma));
// 	memset(mb, -1, sizeof(mb));
// 	int ret = 0;
// 	for (int i = 1; i <= cnt; i++) {
// 		while (!clrS.empty()) {
// 			visitb[clrS.top()] = false;
// 			clrS.pop();
// 		}
// 		if (dfs(i)) ++ret;
// 	}
// 	return ret;
// }

int main() {
	int n, m;
	cin.tie(0)->sync_with_stdio(0);
	cin >> n >> m;
	vector<string> s(n);
	for (int i = 0; i < n; i++) {
		cin >> s[i];
	}
	
	int cnt, cnt2;
	cnt = cnt2 = 0;

	vector a(n, vector<int>(n));
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] != 'R') continue;
			if (j + 2 < m) {
				if (s[i][j + 1] == 'G' && s[i][j + 2] == 'W') {
					++cnt;
					a[i][j] = cnt;
					a[i][j + 1] = cnt;
					a[i][j + 2] = cnt;
				}
			}
			if (i + 2 < n) {
				if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
					++cnt2;
					// b[i][j]= cnt2;
					// b[i + 1][j]= cnt2;
					// b[i + 2][j]= cnt2;
				}
			}
		}
	}

	dinic<int> D(cnt + cnt2 + 2, 0, 1);
	for (int i = 1; i <= cnt; i++) {
		D.add_edge(0, i + 1, 1);
	}
	for (int i = 1; i <= cnt2; i++) {
		D.add_edge(cnt + i + 1, 1, 1);
	}

	int cnt3 = 0;
	for (int i = 0; i < n; i++) {
		for (int j = 0; j < m; j++) {
			if (s[i][j] != 'R') continue;
			if (i + 2 < n) {
				if (s[i + 1][j] == 'G' && s[i + 2][j] == 'W') {
					++cnt3;
					if (a[i][j] != 0) {
						D.add_edge(a[i][j] + 1, cnt + cnt3 + 1, D.INF);
					}
					if (a[i + 1][j] != 0) {
						D.add_edge(a[i + 1][j] + 1, cnt + cnt3 + 1, D.INF);
					}
					if (a[i + 2][j] != 0) {
						D.add_edge(a[i + 2][j] + 1, cnt + cnt3 + 1, D.INF);
					}
					// b[i][j]= cnt2;
					// b[i + 1][j]= cnt2;
					// b[i + 2][j]= cnt2;
				}
			}
		}
	}

	// for (int i = 0; i < n; i++) {
	// 	for (int j = 0; j < m; j++) {
	// 		if (a[i][j] != 0 && b[i][j] != 0) {
	// 			D.add_edge(a[i][j] + 1, cnt + b[i][j] + 1, D.INF);
	// 			// va[a[i][j]].push_back(b[i][j]);
	// 		}
	// 	}
	// }

	cout << cnt + cnt2 - D.max_flow() << endl;
}

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