Submission #770250

#	Time	Username	Problem	Language	Result	Execution time	Memory
770250		gun_gan	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	122 ms	247880 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

const int MX = 3005;

int N, M;
char c[MX][MX];
int e[MX][MX];

vector<int> g[MX * MX];
int col[MX * MX];
int w = 0, b = 0;

void dfs(int v) {
      if(col[v]) b++;
      else w++;

      for(auto u : g[v]) {
            if(col[u] == 2) {
                  col[u] = col[v] ^ 1;
                  dfs(u);
            } else {
                  assert(col[u] == col[v] ^ 1);
            }
      } 
}

int main() {
      cin.tie(0); ios_base::sync_with_stdio(0);

      for(int i = 0; i < MX * MX; i++) col[i] = 2;

      cin >> N >> M;
      for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                  cin >> c[i][j];
            }
      }
      
      // build hori
      int cnt = 0;
      for(int i = 0; i < N; i++) {
            for(int j = 0; j + 2 < M; j++) {
                  if(c[i][j] == 'R' && c[i][j + 1] == 'G' && c[i][j + 2] == 'W') {
                        cnt++;
                        e[i][j] = e[i][j + 1] = e[i][j + 2] = cnt;
                  }
            }
      }

      // build vert and add edge
      for(int j = 0; j < M; j++) {
            for(int i = 0; i + 2 < N; i++) {
                  if(c[i][j] == 'R' && c[i + 1][j] == 'G' && c[i + 2][j] == 'W') {
                        cnt++;
                        if(e[i][j]) {
                              g[cnt].push_back(e[i][j]);
                              g[e[i][j]].push_back(cnt);
                        }
                        if(e[i + 1][j]) {
                              g[cnt].push_back(e[i + 1][j]);
                              g[e[i + 1][j]].push_back(cnt);
                        }
                        if(e[i + 2][j]) {
                              g[cnt].push_back(e[i + 2][j]);
                              g[e[i + 2][j]].push_back(cnt);
                        }
                  }
            }
      }

      // traverse graph
      int ans = 0;
      for(int i = 1; i <= cnt; i++) {
            if(col[i] == 2) {
                  col[i] = 0;
                  w = 0, b = 0;
                  dfs(i);
                  ans += max(w, b);
            }
      }

      cout << ans << '\n';
}

Compilation message (stderr)

In file included from /usr/include/c++/10/cassert:44,
                 from /usr/include/x86_64-linux-gnu/c++/10/bits/stdc++.h:33,
                 from dango_maker.cpp:1:
dango_maker.cpp: In function 'void dfs(int)':
dango_maker.cpp:24:33: warning: suggest parentheses around comparison in operand of '^' [-Wparentheses]
   24 |                   assert(col[u] == col[v] ^ 1);
      |                          ~~~~~~~^~~~~~~~~

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