Submission #508759

#	Time	Username	Problem	Language	Result	Execution time	Memory
508759		cig32	Dango Maker (JOI18_dango_maker)	C++17	33 / 100	960 ms	262148 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 = 1e5 + 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;
}                     
 
unordered_map<int, vector<int> > adj;
vector<int> active;
 
vector<int> v;
unordered_map<int, bool> vis;
 
void dfs(int node) {
    v.push_back(node);
    vis[node] = 1;
    for(int x: adj[node]) {
        if(!vis[x]) dfs(x);
    }
}
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.push_back(id);
              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.push_back(id);
              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+1][j+1] == '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(int x: active) {
      if(!vis[x]) {
          v.clear();
          dfs(x);
          int mi = 1e9, ma = -1e9;
          int cm;
          for(int y: v) {
              int z = (y > n*m ? y - n*m : y);
              if(y > n*m) z = z + m;
              else z++;
              //z:=index
              int r = (z-1) / m + 1;
              int c = (z-1) % m + 1;
              mi = min(mi, r - c);
              ma = max(ma, r - c);
              cm = r + c;
          }
          //cout << mi << " " << ma << " " << cm << "\n";
          map<int, signed> dp[2];
          int r = (cm + mi) / 2;
          int c = (cm - mi) / 2;
          dp[0][mi] = (c>1 && c<m && a[r][c-1] == 'R' && a[r][c+1] == 'W');
          dp[1][mi] = (r>1 && r<n && a[r-1][c] == 'R' && a[r+1][c] == 'W');
          //cout << "(" << r << ", " << c << ") ";
          for(int i=mi + 2; i<=ma; i+=2) {
              r = (cm + i) / 2;
              c = (cm - i) / 2;
              //cout << "(" << r << ", " << c << ") ";
              dp[0][i] = max(
                dp[0][i-2] + (c >= 2 && c < m && a[r][c-1] == 'R' && a[r][c+1] == 'W'),
                dp[1][i-2]
                );
              dp[1][i] = max(
                dp[0][i-2],
                dp[1][i-2] + (r >= 2 && r < n && a[r-1][c] == 'R' && a[r+1][c] == 'W')
                );
          }
          //cout << "\n";
          ans += max(dp[0][ma], dp[1][ma]);
          /*for(int i=mi; i<=ma; i++) cout << dp[0][i] << " ";
          cout << "\n";
          for(int i=mi; i<=ma; i++) cout << dp[1][i] << " ";
          cout << "\n";*/
      }
  }
  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);
} 
/*
10 10
RGWRGWRGWR
WWRGWRGWRG
WRGWRGWRGW
RGWRGWRGWR
GWRGWWGWRG
WRGWRGWRGW
RGWRGWRGWR
GWRGWRGWRG
WRGWRGWRGW
RGWRGWRGWR
 
*/

Compilation message (stderr)

dango_maker.cpp: In function 'void solve(int)':
dango_maker.cpp:83:15: warning: 'cm' may be used uninitialized in this function [-Wmaybe-uninitialized]
   83 |           int cm;
      |               ^~

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