oj.uz

Submission #589091

# Submission time Handle Problem Language Result Execution time Memory
589091 2022-07-04T09:16:19 Z Swan Dango Maker (JOI18_dango_maker) C++14
13 / 100
 1 ms 452 KB 
#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <set>
#include <map>
#include <list>
#include <time.h>
#include <math.h>
#include <random>
#include <deque>
#include <queue>
#include <cassert>
#include <unordered_map>
#include <unordered_set>
#include <iomanip>
#include <bitset>
#include <sstream>
#include <chrono>
#include <cstring>
//#define int long long
#define INP freopen("palpath.in","r",stdin)
#define OUTP freopen("palpath.out","w",stdout)

using namespace std;

int n, m;
const int maxn = 3005;

char arr[maxn][maxn];
int r[maxn][maxn];
int d[maxn][maxn];
bitset<1000000000> used;
int cnt;
vector<vector<int> > v;
int compSize;
int black;

// RGW

void dfs(int u, int color) {
   if (color == 0){
      black++;
   }
   used[u] = 1;
   for(int i = 0; i < v[u].size();i++){
      int to = v[u][i];
      if (!used[to]){
         dfs(to, !color);
      }
   }
}

bool check(int x, int y, char dir) {
   if (x < 0 || x >= n || y < 0 || y >= m) {
      return 0;
   }
   if (dir == 'r') {
      if (y + 2 >= m) {
         return 0;
      }
      if ((arr[x][y] == 'R') && (arr[x][y + 1] == 'G') && (arr[x][y + 2] == 'W')) {
         return 1;
      }
   }
   if (dir == 'd') {
      if (x + 2 >= n) {
         return 0;
      }
      if ((arr[x][y] == 'R') && (arr[x + 1][y] == 'G') && (arr[x + 2][y] == 'W')) {
         return 1;
      }
   }
   return false;
}

int main(){
   ios_base::sync_with_stdio(0);
   cin >> n >> m;
   v.resize(n * m);
   for(int i = 0; i < n;i++) {
      for(int j = 0; j < m;j++) {
         r[i][j] = -1;
         d[i][j] = -1;
         cin >> arr[i][j];
      }
   }
   int ans = 0;
   for(int i = 0; i < n;i++) {
      for(int j = 0; j < m; j++) {
         if (check(i, j, 'r')) {
            r[i][j] = cnt++;
         }
         if (check(i, j, 'd')) {
            d[i][j] = cnt++;
         }
      }
   }
   for(int i = 0; i < n;i++) {
      for(int j = 0; j < m;j++) {
         if (r[i][j] != -1) {
            int node = r[i][j];
            if (check(i, j, 'd')) {
               v[node].push_back(d[i][j]);
            }
            if (check(i - 1, j + 1, 'd')) {
               v[node].push_back(d[i - 1][j + 1]);
            }
            if (check(i - 2, j + 2, 'd')) {
               v[node].push_back(d[i - 2][j + 2]);
            }
         }
         if (d[i][j] != -1) {
            int node = d[i][j];
            if (check(i, j, 'r')) {
               v[node].push_back(r[i][j]);
            }
            if (check(i + 1, j - 1, 'r')) {
               v[node].push_back(r[i + 1][j - 1]);
            }
            if (check(i + 2, j - 2, 'r')) {
               v[node].push_back(r[i + 2][j - 2]);
            }
         }
      }
   }
   if (cnt == 0) {
      cout << 0;
      return 0;
   }
   for(int i = 0; i < cnt; i++) {
      compSize = 0;
      black = 0;
      if (!used[i]){
         dfs(i, 0);
      }
      ans += max(black, compSize - black);
   }
   cout << ans;
   return 0;
}

/* 
1
3
1 3 6
*/

Compilation message

dango_maker.cpp: In function 'void dfs(int, int)':
dango_maker.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |    for(int i = 0; i < v[u].size();i++){
      |                   ~~^~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 328 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 0 ms 328 KB Output is correct

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 328 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 0 ms 328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 1 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 1 ms 340 KB Output is correct
7 Correct 1 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 0 ms 340 KB Output is correct
10 Correct 0 ms 340 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct
13 Correct 0 ms 328 KB Output is correct
14 Correct 0 ms 324 KB Output is correct
15 Correct 1 ms 324 KB Output is correct
16 Correct 0 ms 328 KB Output is correct
17 Correct 1 ms 340 KB Output is correct
18 Correct 1 ms 340 KB Output is correct
19 Correct 1 ms 336 KB Output is correct
20 Correct 1 ms 340 KB Output is correct
21 Correct 1 ms 452 KB Output is correct
22 Incorrect 1 ms 340 KB Output isn't correct
23 Halted 0 ms 0 KB -