제출 #770290

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
770290		gun_gan	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	179 ms	247992 KiB

dango_maker

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

const int MX = 3005;

int N, M;
string c[MX];
int h[MX][MX], v[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++) {
            cin >> c[i];
      }
      
      // 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++;
                        assert(h[i][j] == h[i][j + 1] == h[i][j + 2] == 0);
                        h[i][j] = h[i][j + 1] = h[i][j + 2] = cnt;
                        j += 2;
                  }
            }
      }

      // build vert 
      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++;
                        assert(v[i][j] == v[i + 1][j] == v[i + 2][j] == 0);
                        v[i][j] = v[i + 1][j] = v[i + 2][j] = cnt;

                        i += 2;
                  }
            }
      }

      for(int i = 0; i < N; i++) {
            for(int j = 0; j < M; j++) {
                  if(h[i][j] && v[i][j]) {
                        g[h[i][j]].push_back(v[i][j]);
                        g[v[i][j]].push_back(h[i][j]);
                  }
            }
      }

      assert(cnt <= N * M);

      // 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);
            }
      }

      vector<string> v = 
            {
"RGWRWWRGWR", 
"GWRGWRGWRG", 
"WRGRRGWRGW", 
"RGWRGWRGRR",
"GWRGWRGWRG",
"WRGWRGWRGW",
"RGGRGWGGWR",
"GWRGWRGWRG",
"RRGRWGWWGW",
"RGWRGWRGWR"
            };

      bool is = 1;
      for(int i = 0; i < N; i++) {
            is &= v[i] == c[i];
      }

      if(is) {
            assert(ans == 22);
      } 

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

컴파일 시 표준 에러 (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 'int main()':
dango_maker.cpp:45:40: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   45 |                         assert(h[i][j] == h[i][j + 1] == h[i][j + 2] == 0);
      |                                ~~~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:45:55: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   45 |                         assert(h[i][j] == h[i][j + 1] == h[i][j + 2] == 0);
      |                                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:57:40: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   57 |                         assert(v[i][j] == v[i + 1][j] == v[i + 2][j] == 0);
      |                                ~~~~~~~~^~~~~~~~~~~~~~
dango_maker.cpp:57:55: warning: suggest parentheses around comparison in operand of '==' [-Wparentheses]
   57 |                         assert(v[i][j] == v[i + 1][j] == v[i + 2][j] == 0);
      |                                ~~~~~~~~~~~~~~~~~~~~~~~^~~~~~~~~~~~~~

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