Submission #562948

#	Time	Username	Problem	Language	Result	Execution time	Memory
562948		dattranxxx	Dango Maker (JOI18_dango_maker)	C++11	0 / 100	43 ms	71044 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;
using ll = long long;
const int N = 3000 + 5;
string s[N];
int n, m, d = 0;
int pos[N][N][2]; // left down right up
#define LEFT 0
#define DOWN 1
int tag(int i, int j, int dir) {
	if (i < 0 || j < 0 || i >= n || j >= m) return 0;
	return pos[i][j][dir];
}
vector<int> G[N * N / 3];
int dp[N * N / 3][2];
int c[2];
void call(int u, int e = 0) {
	dp[u][1] = 1;
	for (int v : G[u]) if (v != e)
		call(v, u),
		dp[u][0] += max(dp[v][0], dp[v][1]),
		dp[u][1] += dp[v][0];
}
int main() {
	cin.tie(0)->sync_with_stdio(0); cout.tie(0);
	cin >> n >> m;
	for (int i = 0; i < n; ++i)
		cin >> s[i];
	for (int i = 0; i < n; ++i) for (int j = 0; j < m; ++j) {
		if (j <= m-3 && s[i][j] == 'R' && s[i][j+1] == 'G' && s[i][j+2] == 'W') pos[i][j][LEFT] = ++d;
		if (i <= n-3 && s[i][j] == 'R' && s[i+1][j] == 'G' && s[i+2][j] == 'W') pos[i][j][DOWN] = ++d;
	}
	for (int i = 0, u, v; i < n; ++i) for (int j = 0; j < m; ++j) {
		if (u = pos[i][j][LEFT]) {
			if (v = pos[i][j][DOWN]) G[u].emplace_back(v);
			
			if (v = tag(i-1, j+1, DOWN)) G[u].emplace_back(v);
			if (v = tag(i-2, j+2, DOWN)) G[u].emplace_back(v);
		}
		if (u = pos[i][j][DOWN]) {
			if (v = pos[i][j][LEFT]) G[u].emplace_back(v);
			
			if (v = tag(i+1, j+1, LEFT)) G[u].emplace_back(v);
			if (v = tag(i+2, j+2, LEFT)) G[u].emplace_back(v);
		}
	}
	int res = 0;
	for (int i = 1; i <= d; ++i) if (!dp[i][1]) {
		call(i);
		res += max(dp[i][0], dp[i][1]);
	}
	cout << res;
	return 0;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:34:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   34 |   if (u = pos[i][j][LEFT]) {
      |       ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:35:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   35 |    if (v = pos[i][j][DOWN]) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:37:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   37 |    if (v = tag(i-1, j+1, DOWN)) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:38:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   38 |    if (v = tag(i-2, j+2, DOWN)) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:40:9: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   40 |   if (u = pos[i][j][DOWN]) {
      |       ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:41:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   41 |    if (v = pos[i][j][LEFT]) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:43:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   43 |    if (v = tag(i+1, j+1, LEFT)) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~~~~~
dango_maker.cpp:44:10: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   44 |    if (v = tag(i+2, j+2, LEFT)) G[u].emplace_back(v);
      |        ~~^~~~~~~~~~~~~~~~~~~~~

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