SRM464 Div1 Medium

550
まさかの2-SAT。
論理式にして強連結成分分解? 小さいし、無向だし、律儀にやる必要はなかった。
あまり描く機会がなかったから、気付いても描けなかった。復習しておこう。

const int N = 51 * 2;
bool g[N][N];

int rev(int i, int n){ 
  return (i < n) ? i+n : i-n; 
}

void build_graph(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb, int lim)
{
  const int n = xa.size();
  const int node = n * 2; 
  
  fill( &g[0][0], &g[N-1][N], false );

  for(int i=0; i<node; ++i){
    for(int j=0; j<node; ++j){
      if( i == j )continue;
      int x1 = ( i < n ) ? xa[i] : xb[i-n];
      int y1 = ( i < n ) ? ya[i] : yb[i-n];
      int x2 = ( j < n ) ? xa[j] : xb[j-n];
      int y2 = ( j < n ) ? ya[j] : yb[j-n];     
      g[i][ rev(j, n) ] = abs( x1 - x2 ) < lim && abs( y1 - y2 ) < lim;
    }
  }
  
  return ;
}

void scc(int size)
{
  for(int k=0; k<size; ++k){
    for(int i=0; i<size; ++i){
      for(int j=0; j<size; ++j){
        g[i][j] |= g[i][k] & g[k][j];
      }
    }
  }
  return ;
}

class ColorfulDecoration {
public:
  int getMaximum(vector <int> xa, vector <int> ya, vector <int> xb, vector <int> yb) {

    const int n = xa.size();
    const int node = n * 2;

    int s, b, c;
    s = 0;
    b = 1000100000;

    while( s + 1 < b ){
      c = (s + b) / 2;
      build_graph(xa, ya, xb, yb, c);
      scc(node);
      bool flg = true;
      for(int i=0; i<n; ++i){
        if( g[i][i + n] && g[i + n][i] )flg = false;
      }
      if( flg )s = c;
      else b = c;
    }

    return s;
  }
};