Submission #508690

#	Time	Username	Problem	Language	Result	Execution time	Memory
508690		cig32	Dango Maker (JOI18_dango_maker)	C++17	13 / 100	72 ms	127116 KiB

dango_maker

#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
mt19937_64 rng((int)std::chrono::steady_clock::now().time_since_epoch().count());
const int MAXN = 5.4e6 + 10;
const int MOD = 1e9 + 7;
//#define int long long    

int rnd(int x, int y) { // random number generator
  int u= uniform_int_distribution<int>(x, y)(rng); return u;
}

vector<int> adj[MAXN];
map<int, bool> active;

bool vis[MAXN];
int cnt[2];
void dfs(int node, int cur) {
    cnt[cur]++;
    vis[node] = 1;
    for(int x: adj[node]) {
        if(!vis[x]) dfs(x, 1 - cur);
    }
}
void solve(int tc) {
  int n, m;
  cin >> n >> m;
  char a[n+1][m+1];
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=m; j++) {
          cin >> a[i][j];
      }
  }
  for(int i=1; i<=n; i++) {
      for(int j=1; j<=m; j++) {
          if(j+2 <= m && a[i][j] == 'R' && a[i][j+1] == 'G' && a[i][j+2] == 'W') {
              int id = (i-1) * m + j;
              active[id] = 1;
              if(i+2 <= n && a[i+1][j] == 'G' && a[i+2][j] == 'W') {
                  int id2 = n*m + (i-1) * m + j;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
              if(i >= 2 && i+1 <= n && a[i-1][j+1] == 'R' && a[i+1][j+1] == 'W') {
                  int id2 = n*m + (i-2) * m + j+1;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
              if(i >= 3 && a[i-2][j+2] == 'R' && a[i-1][j+2] == 'G') {
                  int id2 = n*m + (i-3) * m + j+2;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
          }
          if(i+2 <= n && a[i][j] == 'R' && a[i+1][j] == 'G' && a[i+2][j] == 'W') {
              int id = n*m + (i-1) * m + j;
              active[id] = 1;
              if(j+2 <= m && a[i][j+1] == 'G' && a[i][j+2] == 'W') {
                  int id2 = (i-1) * m + j;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
              if(j >= 2 && j+1 <= m && a[i+1][j-1] == 'R' && a[i+2][j-2] == 'W') {
                  int id2 = i * m + j-1;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
              if(j >= 3 && a[i+2][j-2] == 'R' && a[i+2][j-1] == 'G') {
                  int id2 = (i+1) * m + j-2;
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
          }
      }
  }
  int ans = 0;
  for(auto x: active) {
      if(!vis[x.first]) {
          cnt[0] = cnt[1] = 0;
          dfs(x.first, 0);
          ans += max(cnt[0], cnt[1]);
      }
  }
  cout << ans << "\n";
}

int32_t main(){
  ios::sync_with_stdio(0); cin.tie(0);
  int t = 1; //cin >> t;
  for(int i=1; i<=t; i++) solve(i);
} 

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