Submission #528491

#	Time	Username	Problem	Language	Result	Execution time	Memory
528491		georgerapeanu	Dango Maker (JOI18_dango_maker)	C++11	33 / 100	573 ms	262148 KiB

dango_maker

#include <bits/stdc++.h>

using namespace std;

class BipartiteMatcher{
  int n, m;
  vector<int> l;
  vector<int> r;
  vector<vector<int> > graph;
  vector<bool> viz;

  bool pairup(int nod){
    if(viz[nod] == true){
      return false;
    }
    viz[nod] = true;
    for(auto it:graph[nod]){
      if(r[it] == -1){
        l[nod] = it;
        r[it] = nod;
        return true;
      }
    }
    for(auto it:graph[nod]){
      if(pairup(r[it])){
        l[nod] = it;
        r[it] = nod;
        return true;
      }
    }
    return false;
  }

  public:

  BipartiteMatcher(int n, int m) {
    this->n = n;
    this->m = m;
    this->l = vector<int>(n, -1);
    this->r = vector<int>(m, -1);
    this->graph = vector<vector<int> >(n, vector<int>());
    this->viz = vector<bool>(n, false);
  }

  void add_edge(int x, int y){
    graph[x].push_back(y);
  }

  int solve(){
    bool ok = true;

    while(ok){
      ok = false;
      for(int i = 0;i < n;i++){
        viz[i] = false;
      }
      for(int i = 0;i < n;i++){
        if(l[i] == -1 && pairup(i)){
          ok = true;
        }
      }
    }
    int cuplaj = 0;
    for(int i = 0;i < n;i++){
      cuplaj += (l[i] != -1);
    }
    return cuplaj;
  }
};

int main(){
  
    int n, m;
    cin >> n >> m;
    vector<string> v(n,"");
    vector<vector<int> > horizontal_group(n, vector<int>(m, -1));
    vector<vector<int> > vertical_group(n, vector<int>(m, -1));

    for(int i = 0;i < n;i++){
      cin >> v[i];
    }

    int cnt_horizontal = 0;
    int cnt_vertical = 0;

    for(int i = 0;i < n;i++){
      for(int j = 0;j < m;j++){
        if(j + 2 < m && v[i][j] == 'R' && v[i][j + 1] == 'G' && v[i][j + 2] == 'W'){
          horizontal_group[i][j] = cnt_horizontal;
          horizontal_group[i][j + 1] = cnt_horizontal;
          horizontal_group[i][j + 2] = cnt_horizontal;
          cnt_horizontal++;
        }
        if(i + 2 < n && v[i][j] == 'R' && v[i + 1][j] == 'G' && v[i + 2][j] == 'W'){
          vertical_group[i][j] = cnt_vertical;
          vertical_group[i + 1][j] = cnt_vertical;
          vertical_group[i + 2][j] = cnt_vertical;
          cnt_vertical++;
        }
      }
    }

    BipartiteMatcher matcher(cnt_vertical, cnt_horizontal);

    for(int i = 0;i < n;i++){
      for(int j = 0; j < m;j++){
        if(vertical_group[i][j] != -1 && horizontal_group[i][j] != -1){
          matcher.add_edge(vertical_group[i][j], horizontal_group[i][j]);
        }
      }
    }

    printf("%d\n", cnt_horizontal + cnt_vertical - matcher.solve());
    
    return 0;
}

• Subtask 1: 13 / 13
• Subtask 2: 20 / 20
• Subtask 3: 0 / 67