oj.uz

Submission #528487

# Submission time Handle Problem Language Result Execution time Memory
528487 2022-02-20T11:14:26 Z georgerapeanu Dango Maker (JOI18_dango_maker) C++11
0 / 100
 1 ms 332 KB 
#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_horizontal, cnt_vertical);

    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", cnt_horizontal + cnt_vertical - matcher.solve());
    
    return 0;
}

Compilation message

dango_maker.cpp: In member function 'bool BipartiteMatcher::pairup(int)':
dango_maker.cpp:18:16: warning: suggest parentheses around assignment used as truth value [-Wparentheses]
   18 |       if(r[it] = -1){

Subtask #1
0 / 13.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 1 ms 332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #2
0 / 20.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 1 ms 332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -

Subtask #3
0 / 67.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 204 KB Output is correct
2 Correct 1 ms 204 KB Output is correct
3 Correct 0 ms 204 KB Output is correct
4 Correct 0 ms 204 KB Output is correct
5 Correct 0 ms 204 KB Output is correct
6 Correct 0 ms 204 KB Output is correct
7 Runtime error 1 ms 332 KB Execution killed with signal 11
8 Halted 0 ms 0 KB -