Submission #653641

#	Time	Username	Problem	Language	Result	Execution time	Memory
653641		pauloamed	Dango Maker (JOI18_dango_maker)	C++14	33 / 100	296 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;
  bool cap; //
  Edge(int t, bool c, int r, bool irev):to{t},rev{r},cap{c}
  {}
};
 
 
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, (int) 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;
  }
};

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


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

int idv[MAXN][MAXN];
vector<pair<int,int>> es;

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

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

  int curr_idv = 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++;
        }
      }
    }
  }

  int curr_idh = 0;
  for(int i = 0; i < n; ++i){
    for(int j = 0; j < m; ++j){
      if(j + 2 < m){
        if((s[i][j] == 'R') && (s[i][j+1] == 'G') && (s[i][j+2] == 'W')){
          if(idv[i][j] != -1) es.push_back({curr_idh, idv[i][j]});
          if(idv[i][j+1] != -1) es.push_back({curr_idh, idv[i][j+1]});
          if(idv[i][j+2] != -1) es.push_back({curr_idh, idv[i][j+2]});
          curr_idh++;
        }
      }
    }
  }
  // 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);
  }

  while(es.size()){
    auto [a, b] = es.back();
    es.pop_back();
    f.addEdge(b + OFFSET, curr_idv + a + 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 'void Flow::addEdge(int, int, int)':
dango_maker.cpp:36:23: warning: narrowing conversion of 'c' from 'int' to 'bool' [-Wnarrowing]
   36 |     v[a].push_back({b,c,(int)v[b].size(),false});
      |                       ^
dango_maker.cpp: In member function 'int Flow::dfs(int, int)':
dango_maker.cpp:61: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]
   61 |       for(; lastPos[i] < v[i].size(); ++lastPos[i]){
dango_maker.cpp: In function 'int main()':
dango_maker.cpp:155:10: warning: structured bindings only available with '-std=c++17' or '-std=gnu++17'
  155 |     auto [a, b] = es.back();
      |          ^

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