Submission #246172

#	Time	Username	Problem	Language	Result	Execution time	Memory
246172		Nightlight	Dango Maker (JOI18_dango_maker)	C++14	0 / 100	160 ms	190712 KiB

dango_maker

#include <bits/stdc++.h>
using namespace std;
 
const int MAXP = 4000005;
 
int N, M;
vector<int> adj[MAXP];
vector<vector<char>> A;
vector<vector<int>> id;
int match[MAXP];
bitset<MAXP> vis;
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;
}
 
int main() {
  scanf("%d %d", &N, &M);
  A.resize(N + 5);
  id.resize(N + 1);
  for(int i = 1; i <= N; i++) {
    A[i].resize(M + 5);
    id[i].resize(M + 1);
    for(int j = 1; j <= M; j++) {
      scanf(" %c", &A[i][j]);
    }
  }
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      if(A[i][j] == 'G') {
        if(A[i - 1][j] == 'R' && A[i + 1][j] == 'W') {
          if(p >= MAXP) return 69;
          id[i - 1][j] = ++p;
          id[i][j] = p;
          id[i + 1][j] = p;
        }
      }
    }
  }
  for(int i = 1; i <= N; i++) {
    for(int j = 1; j <= M; j++) {
      if(A[i][j] == 'R' && A[i][j + 1] == 'G' && A[i][j + 2] == 'W') {
        if(p >= MAXP) return 69;
        ++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);
      }
    }
    A[i].clear();
    id[i].clear();
  }
  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;
      }
    }
  }
  printf("%d\n", p - cnt);
//  cin >> N;
}

Compilation message (stderr)

dango_maker.cpp: In function 'int main()':
dango_maker.cpp:34: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:41: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: 0 / 13
• Subtask 2: 0 / 20
• Subtask 3: 0 / 67