Submission #473055

#	Time	Username	Problem	Language	Result	Execution time	Memory
473055		ntabc05101	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	1 ms	312 KiB

dango_maker

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

int main() {
  cin.tie(0)->sync_with_stdio(0);

  int n, m; cin >> n >> m;
  string a[n];
  for (int i = 0; i < n; i++) {
    cin >> a[i];
  }

  vector< vector<int> > adj;
  int cnt = 0;
  int vis[n][m];
  memset(vis, -1, sizeof(vis));

  for (int i = 0; i < n; i++) {
    for (int j = 0; j < m - 2; j++) {
      if (a[i][j] == 'R' && a[i][j + 1] == 'G' && a[i][j + 2] == 'W') {
        int cur = cnt;
        adj.push_back(vector<int>());
        cnt++;
        if (i + 2 < n && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
          int a = cnt;
          if (~vis[i + 1][j]) {
            a = vis[i + 1][j];
          }
          else {
            adj.push_back(vector<int>());
            vis[i][j] = vis[i + 1][j] = vis[i + 2][j] = cnt;
            cnt++;
          }
          adj[cur].push_back(a);
          adj[a].push_back(cur);
        }
        if (i + 1 < n && i && a[i + 1][j + 1] == 'W' && a[i - 1][j + 1] == 'R') {
          int a = cnt;
          if (~vis[i + 1][j + 1]) {
            a = vis[i + 1][j + 1];
          }
          else {
            adj.push_back(vector<int>());
            vis[i - 1][j + 1] = vis[i + 1][j + 1] = vis[i][j + 1] = cnt;
            cnt++;
          }
          adj[cur].push_back(a);
          adj[a].push_back(cur);
        }
        if (i > 1 && a[i - 2][j + 2] == 'R' && a[i - 1][j + 2] == 'G') {
          int a = cnt;
          if (~vis[i - 2][j + 2]) {
            a = vis[i - 2][j + 2];
          }
          else {
            adj.push_back(vector<int>());
            vis[i - 2][j + 2] = vis[i - 1][j + 2] = vis[i][j + 2] = cnt;
            cnt++;
          }
          adj[cur].push_back(a);
          adj[a].push_back(cur);
        }
      }
    }
  }
  
  /*for (int i = 0; i < n; i++) {
    for (int j = 0; j < m; j++) {
      cout << setw(5) << vis[i][j];
    }
    cout << "\n";
  }*/

  set< array<int, 2> > st;
  st.insert({0, -1});
  for (int i = 0; i < cnt; i++) {
    auto it = --st.end();
    if (adj[i].size() == 0) {
      st.insert({(*it)[0] + 1, i});
    }
    for (auto &to: adj[i]) {
      if ((*it)[1] == to) {
        it--;
      }
      else {
        st.insert({(*it)[0] + 1, i});
        break;
      }
    }
    while (st.size() > 4) {
      st.erase(st.begin());
    }
  }

  int res = (*(--st.end()))[0];
  
  for (int j = 0; j < m; j++) {
    for (int i = 0; i < n - 2; i++) {
      if (!(~vis[i][j]) && a[i][j] == 'R' && a[i + 1][j] == 'G' && a[i + 2][j] == 'W') {
        res++;
      }
    }
  }

  cout << res << endl;

  return 0;
}

/*
3 4
RGWR
GRGG
RGWW

4 4
RGWR
GRRG
WGGW
WWWR

5 5
RGRGW
GRRGW
WGGWR
RWRGW
RGWGW
*/

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