Submission #653633

#	Time	Username	Problem	Language	Result	Execution time	Memory
653633		pauloamed	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	281 ms	262144 KiB

dango_maker

#include<bits/stdc++.h>
using namespace std;

// Edge structure: handles node pointed to, capacity
// and the index in v[to] to its reverse edge
struct Edge{
  int to, rev;
  int cap; //
  bool is_rev;
  Edge(int t, int c, int r, bool irev):to{t},rev{r},cap{c},is_rev{irev}
  {}
};
 
 
struct Flow{
  int n, s, t; // n: # nodes, s: source, t: sink
  vector<vector<Edge>> v; // extended adj list
  vector<int> lvl; // indicates the lvl for each node. used for the lvl graph
 
  // assures that each edge is completely visited only once. keeps sort of backup
  // of the index of the last visited edge
  // there is no need to revisit an edge, hence, these can be skipped
  vector<int> lastPos;
 
  // constructor
  Flow(int N, int src, int snk){
    this->n = N;
    this->s = src;
    this->t = snk;
    v = vector<vector<Edge>>(n, vector<Edge>());
  }
 
  // adding edges: endpoints and capacities
  // in case of bidirecitonal edges, use this function twice, one for each direction
  // using the full capacity on both
  void addEdge(int a, int b, int c){
    v[a].push_back({b,c,(int)v[b].size(),false});
    v[b].push_back({a,0,((int)v[a].size()) - 1,true});
  }
 
  // "builds" the lvl graph. simple bfs indicating the lvl for each node
  void getLvls(){
    queue<int> q; q.push(s);
    lvl.assign(n,-1); lvl[s] = 0;
    while(q.size()){
      int x = q.front(); q.pop();
      for(auto e : v[x]){
        if(lvl[e.to] == -1 && e.cap){
          // lvl graph only reaches new nodes and possible edges (cap > 0)
          q.push(e.to);
          lvl[e.to] = lvl[x] + 1;
        }
      }
    }
  }
 
  // finds an augmenting path and updates edges
  int dfs(int i, int curr = INT_MAX){
    if(i == t){
      return curr; // reached sink, returning collected flow
    }else{
      for(; lastPos[i] < v[i].size(); ++lastPos[i]){
        auto &e = v[i][lastPos[i]];
        if(e.cap && lvl[i] + 1 == lvl[e.to]){
          // possible edges (cap > 0) and lvl-graph structure (consecutive lvls traversal)
 
          int maybe_flow = dfs(e.to, min(curr, e.cap));
          if(maybe_flow == 0) continue;
 
          e.cap -= maybe_flow; // updating edge
          v[e.to][e.rev].cap += maybe_flow; // and its reverse
          return maybe_flow;
        }
      }
    }
    return 0;
  }
 
  // main funct
  int run(){
    int flow = 0; // initial flow
    while(true){
      getLvls(); // builds lvl graph
      // if the sink cant be reached, the max flow has been found
      if(lvl[t]==-1) break;
      // get a blocking flow for the current lvl graph
      int blocking = -1;
      lastPos.assign(n,0);
      while((blocking = dfs(s))) flow += blocking;
    }
    return flow;
  }
 
  vector<pair<int,int>> get_cut(){
    vector<pair<int,int>> cut;
    for(int i = 0; i < n; ++i){
      for(int j = 0; j < v[i].size(); ++j){
        auto &e = v[i][j];
        if(!e.is_rev && lvl[i] != -1 && lvl[e.to] == -1){
          cut.push_back({i, e.to});
        }
      }
    }
    return cut;
  }
};

const int SRC = 0;
const int SINK = 1;
const int OFFSET = 2;


const int MAXN = 3001;
string s[MAXN];

int idv[MAXN][MAXN];
int idh[MAXN][MAXN];

int main(){
  memset(idv, -1, sizeof idv);
  memset(idh, -1, sizeof idh);

  cin.tie(NULL)->sync_with_stdio(false);
  int n, m; cin >> n >> m;
  for(int i = 0; i < n; ++i){
    cin >> s[i];
  }

  int curr_idv = 0;
  int curr_idh = 0;

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      // ver
      if(i + 2 < n){
        if((s[i][j] == 'R') && (s[i+1][j] == 'G') && (s[i+2][j] == 'W')){
          idv[i][j] = curr_idv;
          idv[i+1][j] = curr_idv;
          idv[i+2][j] = curr_idv;
          curr_idv++;
        }
      }

      if(j + 2 < m){
        if((s[i][j] == 'R') && (s[i][j+1] == 'G') && (s[i][j+2] == 'W')){
          idh[i][j] = curr_idh;
          idh[i][j+1] = curr_idh;
          idh[i][j+2] = curr_idh;
          curr_idh++;
        }
      }
    }
  }

  for(int i = 0; i < n; ++i) s[i].clear();
  // ESQ: VERTICAIS
  // DIR: HORIZONTAIS

  Flow f(2 + curr_idh + curr_idv, SRC, SINK);
  for(int i = 0; i < curr_idv; ++i){
    f.addEdge(SRC, i + OFFSET, 1);
  }
  for(int i = 0; i < curr_idh; ++i){
    f.addEdge(i + curr_idv + OFFSET, SINK, 1);
  }

  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(idh[i][j] != -1 && idv[i][j] != -1){
        // cout << i << " " << j << " " << idv[i][j][0] << " " << idh[i][j][0] << endl;
        f.addEdge(idv[i][j] + OFFSET, curr_idv + idh[i][j] + OFFSET, 1);
      }
    }
  }

  int x = f.run();
  // cout << x << " " << curr_idh << " " << curr_idv<< endl;
  cout << curr_idh + curr_idv - x << "\n";
}

Compilation message (stderr)

dango_maker.cpp: In member function 'int Flow::dfs(int, int)':
dango_maker.cpp:62:24: warning: comparison of integer expressions of different signedness: '__gnu_cxx::__alloc_traits<std::allocator<int>, int>::value_type' {aka 'int'} and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |       for(; lastPos[i] < v[i].size(); ++lastPos[i]){
dango_maker.cpp: In member function 'std::vector<std::pair<int, int> > Flow::get_cut()':
dango_maker.cpp:97:24: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<Edge>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   97 |       for(int j = 0; j < v[i].size(); ++j){
      |                      ~~^~~~~~~~~~~~~

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