Submission #330192

#	Time	Username	Problem	Language	Result	Execution time	Memory
330192		Kevin_Zhang_TW	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	297 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
using ll = long long;
#define pb emplace_back
#define AI(i) begin(i), end(i)
template<class T>
bool chmax(T &a, T b) { return a < b ? (a = b, true) : false; }
template<class T> 
bool chmin(T &a, T b) { return b < a ? (a = b, true) : false; }
#ifdef KEV
#define DE(args...) kout("[ " + string(#args) + " ] = ", args)
void kout() { cerr << endl; }
template<class T, class ...U>
void kout(T a, U ...b) { cerr << a << ' ', kout(b...); }
template<class T>
void debug(T L, T R) { while (L != R) cerr << *L << " \n"[next(L) == R], ++L; }
#else
#define DE(...) 0
#define debug(...) 0
#endif

const int MAX_N = 3005;
char w[MAX_N][MAX_N];
int n, m, a, b, id[MAX_N][MAX_N];
bool valid (char a, char b, char c) { return a == 'R' && b == 'G' && c == 'W'; }
vector<vector<int>> edge;
vector<int> ma;
vector<int> vist;
int Time;
bool dfs(int x) {
	if (vist[x] == Time) return false;
	vist[x] = Time;
	for (int u : edge[x]) if (ma[u] == -1 || dfs(ma[u])) {
		return ma[u] = x, ma[x] = u, true;
	}
	return false;
}
int max_clique(vector<pair<int,int>> alle) {
	b += a;
	edge.resize(b + 1);
	ma.resize(b + 1, -1);
	edge.resize(a + 1);
	vist.resize(b + 1); 

	for (auto [x, y] : alle) {
		edge[x].pb(y + a);
		DE(x, y + a);
	}

	int res = b;
	DE(a, b);

	for (int i = 1;i <= a;++i)
		if (ma[i] == -1 && (Time = i, dfs(i)))
			--res;

	return res; 
}
int solve() {
	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j) { 
			if (valid(w[i][j-1], w[i][j], w[i][j+1])) 
				id[i][j] = ++b; 
		} 
	vector<pair<int,int>> alle;

	for (int i = 1;i <= n;++i)
		for (int j = 1;j <= m;++j) { 
			if (valid(w[i-1][j], w[i][j], w[i+1][j])) {
				++a;
				if (id[i-1][j+1]) 
					alle.pb(a, id[i-1][j+1]);
				if (id[i][j])
					alle.pb(a, id[i][j]);
				if (id[i+1][j-1])
					alle.pb(a, id[i+1][j-1]);
			} 
		}
	return max_clique(alle); 
}
int32_t main() {
	ios_base::sync_with_stdio(0), cin.tie(0);
	cin >> n >> m;
	for (int i = 1;i <= n;++i)
		cin >> w[i] + 1;

	cout << solve() << '\n';
}

Compilation message (stderr)

dango_maker.cpp: In function 'int max_clique(std::vector<std::pair<int, int> >)':
dango_maker.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
dango_maker.cpp:47:3: note: in expansion of macro 'DE'
   47 |   DE(x, y + a);
      |   ^~
dango_maker.cpp:18:17: warning: statement has no effect [-Wunused-value]
   18 | #define DE(...) 0
      |                 ^
dango_maker.cpp:51:2: note: in expansion of macro 'DE'
   51 |  DE(a, b);
      |  ^~
dango_maker.cpp: In function 'int32_t main()':
dango_maker.cpp:85:15: warning: suggest parentheses around '+' inside '>>' [-Wparentheses]
   85 |   cin >> w[i] + 1;
      |          ~~~~~^~~

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