Advertisement
ismaeil

E - Exam Period

Mar 31st, 2023
624
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 4.89 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4.  
  5. // Satisfiability (2SAT)
  6. // given n variable and m clauses (and of ors):
  7. // check if there is any assignment to the vars that satisfy all clauses
  8. // 0-based indexed
  9. // Time Complexity: O(n + m)
  10.  
  11. struct _2Sat {
  12.   // var x is stored in 2x+1 and its negation in 2x
  13.   // use (xor)^ operation to get one from the other
  14.   // from the outside deal with x using index [0 m-1]
  15.   // and booleans to refer to the x or !x
  16.  
  17.   vector<vector<int>> al ,r_al;
  18.   vector<int> topo ,comp;
  19.   vector<bool> vis;
  20.   int n;
  21.  
  22.   // take the number of vars (without the negation of it)
  23.   _2Sat(int m): n(2 * m) {
  24.     topo = vector<int>();
  25.     comp = vector<int>(n);
  26.     al.assign(n ,vector<int>());
  27.     r_al.assign(n ,vector<int>());
  28.   }
  29.  
  30.   // add edge to the graph
  31.   void addEdge(int u ,int v){
  32.     al[u].push_back(v);
  33.     r_al[v].push_back(u);
  34.   }
  35.  
  36.   // at least one of them is true
  37.   void addOrClause(int u1 ,bool x1 ,int u2 ,bool x2) {
  38.     // add edge from !u1 => u2
  39.     addEdge(2 * u1 + !x1 ,2 * u2 + x2);
  40.     // add edge from !u2 => u1
  41.     addEdge(2 * u2 + !x2 ,2 * u1 + x1);
  42.   }
  43.  
  44.   // exactly one of them is true
  45.   void addXorClause(int u1 ,bool x1 ,int u2 ,bool x2) {
  46.     // at least one of u1 and u2 is true
  47.     addOrClause(u1 ,x1 ,u2 ,x2);
  48.     // at least one of !u1 and !u2 is true
  49.     addOrClause(u1 ,!x1 ,u2 ,!x2);
  50.     // the result is exactly one of them is true
  51.   }
  52.  
  53.   // both of them is true (or false)
  54.   void addAndClause(int u1 ,bool x1 ,int u2 ,bool x2){
  55.     // at least one of !u1 and u2 is true
  56.     addOrClause(u1 ,!x1 ,u2 ,x2);
  57.     // at least one of u1 and !u2 is true
  58.     addOrClause(u1 ,x1 ,u2 ,!x2);
  59.     // the result is both of them is true (or false)
  60.   }
  61.  
  62.   // kosaraju algo to find SCCs
  63.   void kosaraju(int u ,bool reverse ,int id = 0) {
  64.     comp[u] = id;
  65.     vis[u] = true;
  66.     vector<int> &adj = reverse ? r_al[u] : al[u];
  67.     for(int v : adj) if( !vis[v] ) kosaraju(v ,reverse ,id);
  68.     topo.push_back(u);
  69.   }
  70.  
  71.   // find if the clauses are satisfiable
  72.   bool satisfiable() {
  73.     bool satisfy = true;
  74.     vis.assign(n ,false);
  75.     for(int u = 0 ; u < n ; u++) if( !vis[u] ) kosaraju(u ,false);
  76.     vis.assign(n ,false);
  77.     for(int i = n - 1 ,id = 0 ; i >= 0 ; i--) if( !vis[topo[i]] ) kosaraju(topo[i] ,true ,id++);
  78.     for(int i = 0 ; i < n / 2 ; i++) satisfy &= (comp[2 * i] != comp[2 * i + 1]);
  79.     return satisfy;
  80.   }
  81.  
  82.   // function that returns a valid vars assignment
  83.   vector<bool> getAns(){
  84.     vector<bool> ans(n / 2);
  85.     for(int i = 0 ; i < n / 2 ; i++) ans[i] = comp[2 * i + 1] > comp[2 * i];
  86.     return ans;
  87.   }
  88. };
  89.  
  90. int main()
  91. {
  92.   int n ,m;
  93.   scanf("%d %d" ,&n ,&m);
  94.  
  95.   _2Sat sat(n);
  96.   bool flag = true;
  97.  
  98.   while( m-- ) {
  99.     char s[2];
  100.     int i ,j ,c;
  101.     scanf("%d %d %s %d" ,&i ,&j ,s ,&c);
  102.     string op = s;
  103.  
  104.     if( op == "<" ){
  105.       if( c == 0 ){
  106.         flag = false;
  107.       } else if( c == 1 ){
  108.         sat.addOrClause(i ,false ,j ,false);
  109.         sat.addAndClause(i ,false ,j ,false);
  110.       } else if( c == 2 ){
  111.         sat.addOrClause(i ,false ,j ,false);
  112.       }
  113.     } else if( op == "<=" ){
  114.       if( c == 0 ){
  115.         sat.addOrClause(i ,false ,j ,false);
  116.         sat.addAndClause(i ,false ,j ,false);
  117.       } else if( c == 1 ){
  118.         sat.addOrClause(i ,false ,j ,false);
  119.       } else if( c == 2 ){
  120.         // accept every thing, nothing to do
  121.       }
  122.     } else if( op == "=" ){
  123.       if( c == 0 ){
  124.         sat.addOrClause(i ,false ,j ,false);
  125.         sat.addAndClause(i ,false ,j ,false);
  126.       } else if( c == 1 ){
  127.         sat.addXorClause(i ,true ,j ,true);
  128.       } else if( c == 2 ){
  129.         sat.addOrClause(i ,true ,j ,true);
  130.         sat.addAndClause(i ,true ,j ,true);
  131.       }
  132.     } else if( op == ">=" ){
  133.       if( c == 0 ){
  134.         // accept every thing, nothing to do
  135.       } else if( c == 1 ){
  136.         sat.addOrClause(i ,true ,j ,true);
  137.       } else if( c == 2 ){
  138.         sat.addOrClause(i ,true ,j ,true);
  139.         sat.addAndClause(i ,true ,j ,true);
  140.       }
  141.     } else if( op == ">" ){
  142.       if( c == 0 ){
  143.         sat.addOrClause(i ,true ,j ,true);
  144.       } else if( c == 1 ){
  145.         sat.addOrClause(i ,true ,j ,true);
  146.         sat.addAndClause(i ,true ,j ,true);
  147.       } else if( c == 2 ){
  148.         flag = false;
  149.       }
  150.     } else if( op == "!=" ){
  151.       if( c == 0 ){
  152.         sat.addOrClause(i ,true ,j ,true);
  153.       } else if( c == 1 ){
  154.         sat.addAndClause(i ,true ,j ,true);
  155.       } else if( c == 2 ){
  156.         sat.addOrClause(i ,false ,j ,false);
  157.       }
  158.     }
  159.   }
  160.  
  161.   puts(flag && sat.satisfiable() ? "Yes" : "No");
  162.   return 0;
  163. }
  164.  
  165. /*
  166. =
  167. 0: 0 0
  168. 1: 1 0 | 0 1
  169. 2: 1 1
  170.  
  171. !=
  172. 0: 1 0 | 0 1 | 1 1
  173. 1: 0 0 | 1 1
  174. 2: 0 0 | 1 0 | 0 1
  175.  
  176. <
  177. 0: impossible
  178. 1: 0 0
  179. 2: 0 0 | 1 0 | 0 1
  180.  
  181. >
  182. 0: 1 0 | 0 1 | 1 1
  183. 1: 1 1
  184. 2: impossible
  185.  
  186. <=
  187. 0: 0 0
  188. 1: 0 0 | 1 0 | 0 1
  189. 2: 0 0 | 1 0 | 0 1 | 1 1
  190.  
  191. >=
  192. 0: 0 0 | 1 0 | 0 1 | 1 1
  193. 1: 1 0 | 0 1 | 1 1
  194. 2: 1 1
  195. */
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement