oj.uz

Submission #508690

# Submission time Handle Problem Language Result Execution time Memory
508690 2022-01-13T14:51:55 Z cig32 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 72 ms 127116 KB 
#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.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 127112 KB Output is correct
2 Correct 65 ms 127112 KB Output is correct
3 Correct 64 ms 127108 KB Output is correct
4 Correct 63 ms 127116 KB Output is correct
5 Correct 63 ms 127112 KB Output is correct
6 Correct 66 ms 127024 KB Output is correct
7 Correct 68 ms 126992 KB Output is correct
8 Correct 62 ms 127096 KB Output is correct
9 Correct 65 ms 127108 KB Output is correct
10 Correct 63 ms 127044 KB Output is correct
11 Correct 65 ms 127104 KB Output is correct
12 Correct 62 ms 127088 KB Output is correct
13 Correct 64 ms 127012 KB Output is correct
14 Correct 72 ms 127044 KB Output is correct
15 Correct 64 ms 127016 KB Output is correct
16 Correct 69 ms 127044 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 127112 KB Output is correct
2 Correct 65 ms 127112 KB Output is correct
3 Correct 64 ms 127108 KB Output is correct
4 Correct 63 ms 127116 KB Output is correct
5 Correct 63 ms 127112 KB Output is correct
6 Correct 66 ms 127024 KB Output is correct
7 Correct 68 ms 126992 KB Output is correct
8 Correct 62 ms 127096 KB Output is correct
9 Correct 65 ms 127108 KB Output is correct
10 Correct 63 ms 127044 KB Output is correct
11 Correct 65 ms 127104 KB Output is correct
12 Correct 62 ms 127088 KB Output is correct
13 Correct 64 ms 127012 KB Output is correct
14 Correct 72 ms 127044 KB Output is correct
15 Correct 64 ms 127016 KB Output is correct
16 Correct 69 ms 127044 KB Output is correct
17 Correct 66 ms 127072 KB Output is correct
18 Correct 63 ms 127060 KB Output is correct
19 Correct 64 ms 127024 KB Output is correct
20 Correct 63 ms 127116 KB Output is correct
21 Correct 64 ms 127112 KB Output is correct
22 Correct 64 ms 127112 KB Output is correct
23 Correct 65 ms 127060 KB Output is correct
24 Correct 63 ms 127032 KB Output is correct
25 Correct 71 ms 127112 KB Output is correct
26 Correct 69 ms 127112 KB Output is correct
27 Correct 66 ms 127092 KB Output is correct
28 Correct 67 ms 127044 KB Output is correct
29 Correct 63 ms 127000 KB Output is correct
30 Correct 72 ms 127092 KB Output is correct
31 Correct 68 ms 127100 KB Output is correct
32 Correct 64 ms 127004 KB Output is correct
33 Correct 66 ms 127012 KB Output is correct
34 Incorrect 64 ms 127036 KB Output isn't correct
35 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 127112 KB Output is correct
2 Correct 65 ms 127112 KB Output is correct
3 Correct 64 ms 127108 KB Output is correct
4 Correct 63 ms 127116 KB Output is correct
5 Correct 63 ms 127112 KB Output is correct
6 Correct 66 ms 127024 KB Output is correct
7 Correct 68 ms 126992 KB Output is correct
8 Correct 62 ms 127096 KB Output is correct
9 Correct 65 ms 127108 KB Output is correct
10 Correct 63 ms 127044 KB Output is correct
11 Correct 65 ms 127104 KB Output is correct
12 Correct 62 ms 127088 KB Output is correct
13 Correct 64 ms 127012 KB Output is correct
14 Correct 72 ms 127044 KB Output is correct
15 Correct 64 ms 127016 KB Output is correct
16 Correct 69 ms 127044 KB Output is correct
17 Correct 66 ms 127072 KB Output is correct
18 Correct 63 ms 127060 KB Output is correct
19 Correct 64 ms 127024 KB Output is correct
20 Correct 63 ms 127116 KB Output is correct
21 Correct 64 ms 127112 KB Output is correct
22 Correct 64 ms 127112 KB Output is correct
23 Correct 65 ms 127060 KB Output is correct
24 Correct 63 ms 127032 KB Output is correct
25 Correct 71 ms 127112 KB Output is correct
26 Correct 69 ms 127112 KB Output is correct
27 Correct 66 ms 127092 KB Output is correct
28 Correct 67 ms 127044 KB Output is correct
29 Correct 63 ms 127000 KB Output is correct
30 Correct 72 ms 127092 KB Output is correct
31 Correct 68 ms 127100 KB Output is correct
32 Correct 64 ms 127004 KB Output is correct
33 Correct 66 ms 127012 KB Output is correct
34 Incorrect 64 ms 127036 KB Output isn't correct
35 Halted 0 ms 0 KB -