oj.uz

답안 #508720

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
508720 2022-01-13T15:52:30 Z cig32 Dango Maker (JOI18_dango_maker) C++17
13 / 100
 1 ms 332 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 = 1e3 + 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];
vector<int> active;

bool vis[MAXN];
int cnt[2];
int col[MAXN];
void dfs(int node, int cur) {
    cnt[cur]++;
    vis[node] = 1;
    col[node] = cur;
    for(int x: adj[node]) {
        if(!vis[x]) dfs(x, 1 - cur);
    }
}
void solve(int tc) {
  for(int i=0; i<MAXN; i++) {
      vis[i] = 0;
      col[i] = 0;
      adj[i].clear();
  }
  active.clear();
  cnt[0] = cnt[1] = 0;
  int n = rnd(1, 10), m = rnd(1, 10);
  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;
                  //cout << id << " " << id2 << " 1\n";
                  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-2] == 'W') {
                  int id2 = i * m + j-1;
                  //cout << id << " " << id2 << " 2\n";
                  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;
                  //cout << id << " " << id2 << " 3\n";
                  adj[id].push_back(id2);
                  adj[id2].push_back(id);
              }
          }
      }
  }
  int ans = 0;
  for(int x: active) {
      if(!vis[x]) {
          cnt[0] = cnt[1] = 0;
          dfs(x, 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);
} 
/*
6 6
RGRWWR
GRRGWR
RRGGGR
WGWRWG
GWGRRR
GRWGGG
*/

Subtask #1
13.0 / 13.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct

Subtask #2
0 / 20.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 216 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 0 ms 332 KB Output is correct
32 Correct 0 ms 332 KB Output is correct
33 Incorrect 0 ms 332 KB Output isn't correct
34 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 332 KB Output is correct
2 Correct 0 ms 256 KB Output is correct
3 Correct 0 ms 332 KB Output is correct
4 Correct 0 ms 332 KB Output is correct
5 Correct 0 ms 332 KB Output is correct
6 Correct 0 ms 332 KB Output is correct
7 Correct 0 ms 332 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 0 ms 332 KB Output is correct
10 Correct 0 ms 332 KB Output is correct
11 Correct 0 ms 332 KB Output is correct
12 Correct 0 ms 332 KB Output is correct
13 Correct 1 ms 332 KB Output is correct
14 Correct 0 ms 332 KB Output is correct
15 Correct 0 ms 332 KB Output is correct
16 Correct 0 ms 332 KB Output is correct
17 Correct 0 ms 216 KB Output is correct
18 Correct 0 ms 332 KB Output is correct
19 Correct 0 ms 332 KB Output is correct
20 Correct 0 ms 332 KB Output is correct
21 Correct 0 ms 332 KB Output is correct
22 Correct 0 ms 332 KB Output is correct
23 Correct 0 ms 332 KB Output is correct
24 Correct 0 ms 332 KB Output is correct
25 Correct 1 ms 332 KB Output is correct
26 Correct 1 ms 332 KB Output is correct
27 Correct 1 ms 332 KB Output is correct
28 Correct 1 ms 332 KB Output is correct
29 Correct 0 ms 332 KB Output is correct
30 Correct 0 ms 332 KB Output is correct
31 Correct 0 ms 332 KB Output is correct
32 Correct 0 ms 332 KB Output is correct
33 Incorrect 0 ms 332 KB Output isn't correct
34 Halted 0 ms 0 KB -