E - Exam Period

#include <bits/stdc++.h>

using namespace std;

// Satisfiability (2SAT)
// given n variable and m clauses (and of ors):
// check if there is any assignment to the vars that satisfy all clauses
// 0-based indexed
// Time Complexity: O(n + m)

struct _2Sat {
  // var x is stored in 2x+1 and its negation in 2x
  // use (xor)^ operation to get one from the other
  // from the outside deal with x using index [0 m-1]
  // and booleans to refer to the x or !x

  vector<vector<int>> al ,r_al;
  vector<int> topo ,comp;
  vector<bool> vis;
  int n;

  // take the number of vars (without the negation of it)
  _2Sat(int m): n(2 * m) {
    topo = vector<int>();
    comp = vector<int>(n);
    al.assign(n ,vector<int>());
    r_al.assign(n ,vector<int>());
  }

  // add edge to the graph
  void addEdge(int u ,int v){
    al[u].push_back(v);
    r_al[v].push_back(u);
  }

  // at least one of them is true
  void addOrClause(int u1 ,bool x1 ,int u2 ,bool x2) {
    // add edge from !u1 => u2
    addEdge(2 * u1 + !x1 ,2 * u2 + x2);
    // add edge from !u2 => u1
    addEdge(2 * u2 + !x2 ,2 * u1 + x1);
  }

  // exactly one of them is true
  void addXorClause(int u1 ,bool x1 ,int u2 ,bool x2) {
    // at least one of u1 and u2 is true
    addOrClause(u1 ,x1 ,u2 ,x2);
    // at least one of !u1 and !u2 is true
    addOrClause(u1 ,!x1 ,u2 ,!x2);
    // the result is exactly one of them is true
  }

  // both of them is true (or false)
  void addAndClause(int u1 ,bool x1 ,int u2 ,bool x2){
    // at least one of !u1 and u2 is true
    addOrClause(u1 ,!x1 ,u2 ,x2);
    // at least one of u1 and !u2 is true
    addOrClause(u1 ,x1 ,u2 ,!x2);
    // the result is both of them is true (or false)
  }

  // kosaraju algo to find SCCs
  void kosaraju(int u ,bool reverse ,int id = 0) {
    comp[u] = id;
    vis[u] = true;
    vector<int> &adj = reverse ? r_al[u] : al[u];
    for(int v : adj) if( !vis[v] ) kosaraju(v ,reverse ,id);
    topo.push_back(u);
  }

  // find if the clauses are satisfiable
  bool satisfiable() {
    bool satisfy = true;
    vis.assign(n ,false);
    for(int u = 0 ; u < n ; u++) if( !vis[u] ) kosaraju(u ,false);
    vis.assign(n ,false);
    for(int i = n - 1 ,id = 0 ; i >= 0 ; i--) if( !vis[topo[i]] ) kosaraju(topo[i] ,true ,id++);
    for(int i = 0 ; i < n / 2 ; i++) satisfy &= (comp[2 * i] != comp[2 * i + 1]);
    return satisfy;
  }

  // function that returns a valid vars assignment
  vector<bool> getAns(){
    vector<bool> ans(n / 2);
    for(int i = 0 ; i < n / 2 ; i++) ans[i] = comp[2 * i + 1] > comp[2 * i];
    return ans;
  }
};

int main()
{
  int n ,m;
  scanf("%d %d" ,&n ,&m);

  _2Sat sat(n);
  bool flag = true;

  while( m-- ) {
    char s[2];
    int i ,j ,c;
    scanf("%d %d %s %d" ,&i ,&j ,s ,&c);
    string op = s;

    if( op == "<" ){
      if( c == 0 ){
        flag = false;
      } else if( c == 1 ){
        sat.addOrClause(i ,false ,j ,false);
        sat.addAndClause(i ,false ,j ,false);
      } else if( c == 2 ){
        sat.addOrClause(i ,false ,j ,false);
      }
    } else if( op == "<=" ){
      if( c == 0 ){
        sat.addOrClause(i ,false ,j ,false);
        sat.addAndClause(i ,false ,j ,false);
      } else if( c == 1 ){
        sat.addOrClause(i ,false ,j ,false);
      } else if( c == 2 ){
        // accept every thing, nothing to do
      }
    } else if( op == "=" ){
      if( c == 0 ){
        sat.addOrClause(i ,false ,j ,false);
        sat.addAndClause(i ,false ,j ,false);
      } else if( c == 1 ){
        sat.addXorClause(i ,true ,j ,true);
      } else if( c == 2 ){
        sat.addOrClause(i ,true ,j ,true);
        sat.addAndClause(i ,true ,j ,true);
      }
    } else if( op == ">=" ){
      if( c == 0 ){
        // accept every thing, nothing to do
      } else if( c == 1 ){
        sat.addOrClause(i ,true ,j ,true);
      } else if( c == 2 ){
        sat.addOrClause(i ,true ,j ,true);
        sat.addAndClause(i ,true ,j ,true);
      }
    } else if( op == ">" ){
      if( c == 0 ){
        sat.addOrClause(i ,true ,j ,true);
      } else if( c == 1 ){
        sat.addOrClause(i ,true ,j ,true);
        sat.addAndClause(i ,true ,j ,true);
      } else if( c == 2 ){
        flag = false;
      }
    } else if( op == "!=" ){
      if( c == 0 ){
        sat.addOrClause(i ,true ,j ,true);
      } else if( c == 1 ){
        sat.addAndClause(i ,true ,j ,true);
      } else if( c == 2 ){
        sat.addOrClause(i ,false ,j ,false);
      }
    }
  }

  puts(flag && sat.satisfiable() ? "Yes" : "No");
  return 0;
}

/*
=
0: 0 0
1: 1 0 | 0 1
2: 1 1

!=
0: 1 0 | 0 1 | 1 1
1: 0 0 | 1 1
2: 0 0 | 1 0 | 0 1

<
0: impossible
1: 0 0
2: 0 0 | 1 0 | 0 1

>
0: 1 0 | 0 1 | 1 1
1: 1 1
2: impossible

<=
0: 0 0
1: 0 0 | 1 0 | 0 1
2: 0 0 | 1 0 | 0 1 | 1 1

>=
0: 0 0 | 1 0 | 0 1 | 1 1
1: 1 0 | 0 1 | 1 1
2: 1 1
*/