lib/Documentation/docs-sonyckson/10319.cpp

   1 // 2 SAT :)
   2
   3 #include <cstdio>
   4 #include <cstdlib>
   5 #include <vector>
   6 #include <stack>
   7 using namespace std;
   8 #define MED 50
   9 #define N 100
  10 vector<int> edges[2*N + 30];
  11 int CC[210], id[210];
  12 int tipo[210];
  13 stack<int> pila;
  14 int ID;
  15 int SCC = 0;
  16
  17
  18 int DFS3(int node){
  19         id[node] = ID++;
  20         int minid = id[node];
  21         tipo[node] = 1;
  22         pila.push(node);
  23         for(int i = 0 ; i < edges[node].size() ; i++ ){
  24                 int w = edges[node][i];
  25                 if( tipo[w] == 0 ) minid = min ( minid, DFS3(w));
  26                 else if( tipo[w] == 1 ) minid = min ( minid, id[w]);
  27         }
  28         if( minid == id[node] ){
  29                 SCC++;
  30                 while(1){
  31                         int n = pila.top(); CC[n] = SCC;pila.pop();
  32                         if( n == node ) break;
  33                 }
  34         }
  35         tipo[node] = 2;
  36         return minid;
  37 }
  38
  39
  40 int main(){
  41         int i,j ,k;
  42         int casos;
  43         scanf("%i", &casos);
  44         for(int h = 0; h < casos; h ++){
  45                 for(i=0;i<2*N+30;i++) edges[i].clear();
  46                 SCC = 0;
  47                 int row, col, cant;
  48                 scanf("%i %i %i", &row, &col, &cant);
  49                 int f1, c1, f2, c2;
  50                 for(i=0;i<cant;i++){
  51                         scanf("%i %i %i %i", &f1, &c1, &f2, &c2);
  52                         c1 = MED + c1;
  53                         c2 = MED + c2;
  54                         if( c1 == c2 ){
  55                                 if( f1 < f2 ){
  56                                         // agrego c1 o c1...
  57                                         edges[N+c1].push_back(c1);
  58                                 }else if( f2 < f1 ){
  59 //                                      printf("col = %i %i %i %i\n", f1, c1, f2, c2);
  60                                         edges[c1].push_back(N+c1);
  61                                 }
  62                                 continue;
  63                         }
  64                         if( f1 == f2 ){
  65                                 if( c1 < c2 ){
  66                                         // agrego f1 o f1...
  67                                         edges[N+f1].push_back(f1);
  68                                 }else if( c2 < c1 ){
  69 //                                      printf("fila = %i %i %i %i\n", f1, c1, f2, c2);
  70                                         edges[f1].push_back(N+f1);
  71                                 }
  72                         }else if( f1 < f2 ){
  73                                 if( c1 < c2 ){
  74                                         edges[N+f1].push_back(f2);
  75                                         edges[N+f1].push_back(c1);
  76                                         edges[N+c2].push_back(f2);
  77                                         edges[N+c2].push_back(c1);
  78                                         edges[N+f2].push_back(f1);
  79                                         edges[N+f2].push_back(c2);
  80                                         edges[N+c1].push_back(f1);
  81                                         edges[N+c1].push_back(c2);
  82                                 }else{
  83                                         edges[f1].push_back(N+f2);
  84                                         edges[f1].push_back(c1);
  85                                         edges[N+c2].push_back(N+f2);
  86                                         edges[N+c2].push_back(c1);
  87                                         edges[f2].push_back(N+f1);
  88                                         edges[f2].push_back(c2);
  89                                         edges[N+c1].push_back(N+f1);
  90                                         edges[N+c1].push_back(c2);
  91                                 }
  92                         }else{
  93                                 if( c1 < c2 ){
  94                                         edges[N+f1].push_back(f2);
  95                                         edges[N+f1].push_back(N+c1);
  96                                         edges[c2].push_back(f2);
  97                                         edges[c2].push_back(N+c1);
  98                                         edges[N+f2].push_back(f1);
  99                                         edges[N+f2].push_back(N+c2);
 100                                         edges[c1].push_back(f1);
 101                                         edges[c1].push_back(N+c2);
 102                                 }else{
 103                                         edges[f1].push_back(N+f2);
 104                                         edges[f1].push_back(N+c1);
 105                                         edges[c2].push_back(N+f2);
 106                                         edges[c2].push_back(N+c1);
 107                                         edges[f2].push_back(N+f1);
 108                                         edges[f2].push_back(N+c2);
 109                                         edges[c1].push_back(N+f1);
 110                                         edges[c1].push_back(N+c2);
 111                                 }
 112                         }
 113                 }
 114                 int ID = 1;
 115                 int vale = 1;
 116                 memset(CC, -1, sizeof(CC));
 117                 memset(id, -1, sizeof(id));
 118                 memset(tipo, 0, sizeof(tipo));
 119                 for(i=1;i<=row;i++){
 120                         if( CC[i] < 0 ) DFS3(i);
 121                         if( CC[i + N] < 0 ) DFS3(i + N);
 122                         if( CC[i] == CC[i+N] ) vale = 0;
 123                 }
 124
 125                 for(i=MED+1;i<= MED + col;i++){
 126                         if( CC[i] < 0 ) DFS3(i);
 127                         if( CC[i + N]< 0 ) DFS3(i + N);
 128                         if( CC[i] == CC[i+N] ) vale = 0;
 129                 }
 130
 131                 if( vale ) printf("Yes\n");
 132                 else printf("No\n");
 133         }
 134         return 0;
 135 }