E - Exam Period

Mar 31st, 2023
521
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
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
48.     // at least one of !u1 and !u2 is true
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
57.     // at least one of u1 and !u2 is true
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 ){
110.       } else if( c == 2 ){
112.       }
113.     } else if( op == "<=" ){
114.       if( c == 0 ){
117.       } else if( c == 1 ){
119.       } else if( c == 2 ){
120.         // accept every thing, nothing to do
121.       }
122.     } else if( op == "=" ){
123.       if( c == 0 ){
126.       } else if( c == 1 ){
128.       } else if( c == 2 ){
131.       }
132.     } else if( op == ">=" ){
133.       if( c == 0 ){
134.         // accept every thing, nothing to do
135.       } else if( c == 1 ){
137.       } else if( c == 2 ){
140.       }
141.     } else if( op == ">" ){
142.       if( c == 0 ){
144.       } else if( c == 1 ){
147.       } else if( c == 2 ){
148.         flag = false;
149.       }
150.     } else if( op == "!=" ){
151.       if( c == 0 ){
153.       } else if( c == 1 ){
155.       } else if( c == 2 ){
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. */