# HackerEarth Alice and wheel-graph problem solution

In this HackerEarth Alice and wheel-graph problem solution Alice has a wheel-graph: an undirected graph with n + 1 nodes and 2 . n edges. In wheel-graph there are edges between n + 1 and i for each integer i : 1 <= i <= n and edges between i and i mod n + 1 for each integer i : 1 <= i <= n (see examples to understand it better). Undirected graphs are quite boring for Alice so she made a directed wheel-graph and now each edge has a direction.

Alice wants performs two types of queries:
• 1 a b - change orientation between nodes a and b. Now orientation is from a to b (before this query in graph was a edge from node b to node a).
• 2 a b - check if is b reachable from a.
Help her.

## HackerEarth Alice and wheel-graph problem solution.

`#include <iostream>#include <cstdio>#include <cstdlib>#include <cstring>#include <string>#include <vector>#include <algorithm>#include <set>#include <map>#include <cmath>#include <ctime>#include <functional>#include <sstream>#include <fstream>#include <valarray>#include <complex>#include <queue>#include <cassert>#include <bitset>using namespace std;#ifdef LOCAL#define debug_flag 1#else#define debug_flag 0#endif  template <class T1, class T2 >std::ostream& operator << (std::ostream& os, const pair<T1, T2> &p) {  os << "[" << p.first << ", " << p.second << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::vector<T>& v) {  os << "[";  bool first = true;  for (typename std::vector<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}  template <class T >std::ostream& operator << (std::ostream& os, const std::set<T>& v) {  os << "[";  bool first = true;  for (typename std::set<T>::const_iterator it = v.begin(); it != v.end(); ++it)  {    if (!first)      os << ", ";    first = false;    os << *it;  }  os << "]";  return os;}#define dbg(args...) { if (debug_flag) { _print(_split(#args, ',').begin(), args); cerr << endl; } else { void(0);} }vector<string> _split(const string& s, char c) {  vector<string> v;  stringstream ss(s);  string x;  while (getline(ss, x, c))    v.emplace_back(x);  return v;}void _print(vector<string>::iterator) {}template<typename T, typename... Args>void _print(vector<string>::iterator it, T a, Args... args) {  string name = it -> substr((*it)[0] == ' ', it -> length());  if (isalpha(name[0]))    cerr << name  << " = " << a << " ";  else    cerr << name << " ";  _print(++it, args...);}typedef long long int int64;struct Graph{  int n;  set<int> no_right_s;  set<int> no_left_s;  set<int> to_center_s;  vector<pair<int, int> > segments;  Graph(int new_n = 0)  {    n = new_n;  }  void change_edge(int a, int b)  {    if (a == n)    {      to_center_s.erase(b);    }    else if (b == n)    {      to_center_s.insert(a);    }    else if ((a + 1) % n == b)    {      no_right_s.erase(a);      no_left_s.insert(b);    }    else    {      no_left_s.erase(a);      no_right_s.insert(b);    }  }  bool can_reach_center(int a)  {    if (a == n)      return true;    segments.clear();    add_reachable_to_right(a);    add_reachable_to_left(a);    for (pair<int, int> segment : segments)    {      int l = segment.first;      int r = segment.second;      auto it = to_center_s.lower_bound(l);      if (it != to_center_s.end() && *it <= r)        return true;    }    return false;  }  void add_reachable_to_right(int a)  {    if (no_right_s.empty())    {      segments.clear();      segments.emplace_back(0, n - 1);      return;    }    auto it = no_right_s.lower_bound(a);    if (it != no_right_s.end())    {      segments.emplace_back(a, *it);      return;    }    segments.emplace_back(a, n - 1);    if (no_right_s.count(n - 1) == 1 || a == 0)      return;    it = no_right_s.lower_bound(0);    if (it == no_right_s.end())      segments.emplace_back(0, a - 1);    else      segments.emplace_back(0, *it);  }  void add_reachable_to_left(int a)  {    if (no_left_s.empty())    {      segments.clear();      segments.emplace_back(0, n - 1);      return;    }    auto it = no_left_s.upper_bound(a);    if (it != no_left_s.begin())    {      it--;      segments.emplace_back(*it, a);      return;    }    segments.emplace_back(0, a);    if (no_left_s.count(0) == 1 || a == n - 1)      return;    it = no_left_s.end();    it--;    segments.emplace_back(*it, n - 1);  }};int n;Graph graph, reverse_graph;bool can_reach(int a, int b){  bool can_reach_center_b = reverse_graph.can_reach_center(b);  if (a == n)    return can_reach_center_b;     bool can_reach_center_a = graph.can_reach_center(a);  if (b == n)    return can_reach_center_a;  if (can_reach_center_a && can_reach_center_b)    return true;  for (pair<int, int> segment : graph.segments)  {    int l = segment.first;    int r = segment.second;    if (l <= b && b <= r)      return true;  }  return false;}int main(){#ifdef LOCAL  freopen ("input.txt", "r", stdin);#endif  scanf("%d", &n);  graph = Graph(n);  reverse_graph = Graph(n);  for (int i = 0; i < 2 * n; i++)  {    int a, b;    scanf("%d%d", &a, &b);    a--;    b--;    graph.change_edge(a, b);    reverse_graph.change_edge(b, a);  }  int q;  scanf("%d", &q);  for (int i = 0; i < q; i++)  {    int type, a, b;    scanf("%d%d%d", &type, &a, &b);    a--;    b--;    if (type == 1)    {      graph.change_edge(a, b);      reverse_graph.change_edge(b, a);    }    else    {      bool res = can_reach(a, b);      printf("%s\n", res ? "Yes" : "No");    }  }  return 0;}`