oj.uz

Submission #246202

# Submission time Handle Problem Language Result Execution time Memory
246202 2020-07-08T10:52:12 Z Nightlight Dango Maker (JOI18_dango_maker) C++14
13 / 100
 6 ms 592 KB 
#include <bits/stdc++.h>
using namespace std;

const int MAXP = 6005;

int N, M;
vector<int> adj[MAXP];
char A[3005][3005];
int id[3001][3001];
int match[MAXP];
bitset<MAXP> vis;
int ans = 0;
int p;

void edge(int u, int v) {
//  cout << u << " " << v << "\n";
  adj[u].emplace_back(v);
  adj[v].emplace_back(u);
}

int kuhn(int u) {
  if(vis[u]) return 0;
  vis[u] = 1;
  for(int v : adj[u]) {
    if(match[v] == 0 || kuhn(match[v])) {
      match[u] = v;
      match[v] = u;
      return 1;
    }
  }
  return 0;
}

void maxmatch(int offset) {
  for(int i = 1, j = offset - 1; i <= offset; i++, j--) {
    if(A[i][j] == 'R' && A[i + 1][j] == 'G' && A[i + 2][j] == 'W') {
      id[i][j] = ++p;
      id[i + 1][j] = p;
      id[i + 2][j] = p;
    }
  }
  for(int i = 1, j = offset - 1; i <= offset; i++, j--) {
    if(A[i][j] == 'R' && A[i][j + 1] == 'G' && A[i][j + 2] == 'W') {
      ++p;
      if(id[i][j]) edge(id[i][j], p);
      if(id[i][j + 1]) edge(id[i][j + 1], p);
      if(id[i][j + 2]) edge(id[i][j + 2], p);
    }
  }
  bool ok = 0;
  int cnt = 0;
  while(ok == 0) {
    ok = 1;
    vis = 0;
    for(int i = 1; i <= p; i++) {
      if(match[i] == 0 && kuhn(i)) {
        cnt++;
        ok = 0;
      }
    }
  }
  for(int i = 1; i <= p; i++) {
    adj[p].clear();
    match[p] = 0;
  }
  ans += p - cnt;
  p = 0;
}

int main() {
  scanf("%d %d", &N, &M);
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      scanf(" %c", &A[i][j]);
    }
  }
  for(int i = 2; i <= N + M; i++) maxmatch(i);
  printf("%d\n", ans);
  cin >> N;
}

Compilation message

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:71:8: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %d", &N, &M);
   ~~~~~^~~~~~~~~~~~~~~~~
dango_maker.cpp:74:12: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
       scanf(" %c", &A[i][j]);
       ~~~~~^~~~~~~~~~~~~~~~~

Subtask #1
13.0 / 13.0

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

Subtask #2
0 / 20.0

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

Subtask #3
0 / 67.0

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