Codeforces Round 884 (Div. 1 + Div. 2) - E. Great Grids

E. Great Grids

각 $2 \times 2$ 의 격자에 대각선으로 두 방향중 하나를 결정해야 한다.

$1,2$ 행의 그러한 생김새를 결정했다고 하자.

$2, 3$행을 보면 다음과 같이 두 가지 경우만 가능하다.

이러한 관찰로 우리는 모든 행에 대해서 두 가지중 하나의 대각선 배치를 가진다는 것을 알 수 있고, 이는 열에 대해서도 동일하다.

이러한 배치가 나올 때가 왜 필요충분조건인지는 에디토리얼에서 a,b,c에 0,1,2를 붙이고 modulo 3를 이용해 증명하는 것으로 기재되어있다.

실제 저 행이나 열의 대각선 배치는 중요하지 않고 중요한 것은 모든 행이 두 가지 배치 중 하나를 가진다는 것이다.

따라서 이는 2-colourability 문제로 치환될 수 있다. DSU로 생각해보자.

총 $2(N+M)$ 개의 정점이 있다고 하고 각각 다음을 나타낸다고 하자.

• $1 \sim N$ : $i$ 번째 행이 첫 번째 타입
• $N+1 \sim N+M$ : $j$ 번째 열이 첫 번째 타입
• $N+M+1 \sim2N+M$ : $i$ 번째 행일 두 번째 타입
• $2N+M+1 \sim 2N+2M$ : $j$ 번째 행이 두 번째 타입

$K$ 개의 조건으로 인해 대각선이 하나 그어진다고 하자. 이 때 $(y_1,x_1)\ , \ (y_2,x_2)$ 라 하자.

오른쪽 아래로 그어지는 대각선이 현재 행과 열이 같은 타입을 가지고 있다는 것을 의미한다고 정의한다.

$y_1, x_1+N$ 와 $y_1+N+M, x_1+2N+M$ 을 이어줄 수 있다.

반대도 비슷하게 해준다.

struct DSU {  
   vector<int> p;  
   DSU(int n) : p(n, -1) {}  
   int gp(int n) {  
      if (p[n] < 0) return n;  
      return p[n] = gp(p[n]);  
   }  
   void merge(int a, int b, int to_b = 0) {  
      a = gp(a), b = gp(b);  
      if (a == b) return;  
      if (!to_b && size(a) > size(b)) swap(a, b);  
      p[b] += p[a];  
      p[a] = b;  
   }  
   bool is_merged(int a, int b) { return gp(a) == gp(b); }  
   int size(int n) { return -p[gp(n)]; }  
};  
void solve() {  
   int Y, X, K;  
   cin >> Y >> X >> K;  
  
   DSU dsu(2 * (Y + X));  
  
   for (int i = 0; i < K; i++) {  
      int y1, x1, y2, x2;  
      cin >> y1 >> x1 >> y2 >> x2;  
      y1--, x1--, y2--, x2--;  
      int y = min(y1, y2), x = min(x1, x2);  
      int cross = y1 + x1 == y2 + x2;  
      if (!cross) {  
         dsu.merge(y, x + Y);  
         dsu.merge(y + Y + X, x + Y + X + Y);  
      } else {  
         dsu.merge(y, x + Y + X + Y);  
         dsu.merge(y + Y + X, x + Y);  
      }  
   }  
  
   int fail = 0;  
   for (int i = 0; i < Y + X; i++) {  
      if (dsu.is_merged(i, i + Y + X)) fail = 1;  
   }  
   if (fail) cout << "NO\n";  
   else cout << "YES\n";  
}