fork download
copy 
  1. #include <string>
  2. #include <vector>
  3. #include <algorithm>
  4. #include <numeric>
  5. #include <set>
  6. #include <map>
  7. #include <queue>
  8.  
  9. #include<stack>
  10. #include<bitset>
  11. #include <iostream>
  12. #include <sstream>
  13. #include <cstdio>
  14. #include <cmath>
  15. #include <ctime>
  16. #include <cstring>
  17. #include <cctype>
  18. #include <cassert>
  19. #include <limits>
  20. #include <functional>
  21. #include<unordered_map>
  22.  
  23. #define rep(i,n) for(int (i)=0;(i)<(int)(n);++(i))
  24. #define rer(i,l,u) for(int (i)=(int)(l);(i)<=(int)(u);++(i))
  25. #define reu(i,l,u) for(int (i)=(int)(l);(i)<(int)(u);++(i))
  26. #define aut(r,v) for(auto r:v)
  27.  
  28. #define each(it,o) for(aut(it, (o).begin()); it != (o).end(); ++ it)
  29. #define all(o) (o).begin(), (o).end()
  30. #define pb(x) push_back(x)
  31. #define pc()  pop_back()
  32.  
  33. #define ull unsigned long long
  34. #define mp(x,y) make_pair((x),(y))
  35. #define mset(m,v) memset(m,v,sizeof(m))
  36.  
  37. #define INF 0x3f3f3f3f
  38. #define INFL 0x3f3f3f3f3f3f3f3fLL
  39. using namespace std;
  40. #define ll long long
  41. #define endl '\n'
  42.  
  43. #define st stack<int>
  44.  
  45.  
  46.  
  47. #define vl vector<long long>
  48. #define vi vector<int>
  49. #define vb vector<bool>
  50. #define vc vector<char>
  51. #define pii pair<int,int>
  52. #define vpii vector<pii>
  53. #define vvi vector<vi>
  54. #define vs vector<string>
  55.  
  56. #define mod 1000000007
  57.  
  58. #define un  unordered_map<int,int>
  59. #define mii map<int,int>
  60.  
  61. #define Sort(a) sort(all(a))
  62. #define ED(a) Sort(a), a.erase(unique(all(a)), a.end())//removing all duplicates
  63.  
  64. #define max3(a, b, c)   max(a, max(b, c))
  65. #define min3(a, b, c)   min(a, min(b, c))
  66. #define Max(a)       *max_element(all(a))
  67. #define Min(a)       *min_element(all(a))
  68. #define MaxP(a)       max_element(all(a)) - a.begin()
  69. #define MinP(a)        min_element(all(a)) - a.begin()
  70.  
  71. #define allUpper(a)     transform(all(a), a.begin(), :: toupper)
  72. #define allLower(a)     transform(all(a), a.begin(), :: tolower)
  73.  
  74. #define rev(a)          reverse(all(a))
  75. #define ub(v,k)          upper_bound(all(v), k) - v.begin()
  76. #define lb(v,k)          lower_bound(all(v), k) - v.begin()
  77. #define adv(a,n)        advance(auto it:a,n)
  78. #define RSort(a)         sort(a.rbegin(),a.rend()) //decending order
  79. #define cnt(v,a)             count(all(v),a)
  80. #define bs(v,a)           binary_search(all(v),a)
  81. #define mmax(v)           *max_element(all(v))
  82. #define mmin(v)           *min_element(all(v))
  83. #define popcount(mask)                       __builtin_popcount(mask) // count set bit
  84. #define popcountLL(mask)                     __builtin_popcountll(mask) // for long long
  85. #define X real() // useful for working with #include <complex> for computational geometry
  86. #define Y imag()
  87.  
  88. #define ss second
  89. #define ff first
  90.  
  91. #define trace1(x)                           cerr << #x << ": " << x << endl;
  92. #define trace2(x, y)                        cerr << #x << ": " << x << " | " << #y << ": " << y << endl;
  93. #define trace3(x, y, z)                     cerr << #x << ": " << x << " | " << #y << ": " << y << " | " << #z << ": " << z << endl;
  94. #define trace4(a, b, c, d)                  cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << endl;
  95. #define trace5(a, b, c, d, e)               cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << endl;
  96. #define trace6(a, b, c, d, e, f)            cerr << #a << ": " << a << " | " << #b << ": " << b << " | " << #c << ": " << c << " | " << #d << ": " << d << " | " << #e << ": " << e << " | " << #f << ": " << f << endl;
  97.  
  98. template <typename T> T gcd(T a, T b) { while (b) b ^= a ^= b ^= a %= b; return a; }
  99. template <typename T> T setbit(T mask, T pos) { return mask |= (1 << pos); }
  100. template <typename T> T resetbit(T mask, T pos) { return mask &= ~(1 << pos); }
  101. template <typename T> T togglebit(T mask, T pos) { return mask ^= (1 << pos); }
  102. template <typename T> T checkbit(T mask, T pos) { return (bool)(mask & (1 << pos)); }
  103. template <typename T> T lcm(T a, T b) { return (a / gcd(a, b)) * b; }
  104.  
  105.  
  106.  
  107. template <typename T> T modu(T a, T b) { return (a < b ? a : a % b); }
  108. template<typename T> T mod_neg(T a, T b) { a = mod(a, b); if (a < 0) { a += b; } return a; }
  109.  
  110. template <typename T>T expo(T e, T n) { T x = 1, p = e; while (n) { if (n & 1)x = x * p; p = p * p; n >>= 1; } return x; }
  111. template<typename T> T mod_inverse(T a, T n) { T x, y; T d = extended_euclid(a, n, x, y); return (d > 1 ? -1 : mod_neg(x, n)); }
  112.  
  113. template <typename T>T power(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mod(x * p, m); p = mod(p * p, m); n >>= 1; } return x; }
  114. template <typename T>T powerL(T e, T n, T m) { T x = 1, p = e; while (n) { if (n & 1)x = mulmod(x, p, m); p = mulmod(p, p, m); n >>= 1; } return x; }
  115.  
  116. bool Pow2(int n) {
  117.     return n && (!(n & (n - 1)));
  118. }
  119. void printc(vc& result) {
  120.     aut(r, result) cout << r << " ";
  121.     cout << endl;
  122. }
  123. void printl(vl& result) {
  124.     aut(r, result) cout << r << " ";
  125.     cout << endl;
  126. }
  127. void print(vi& result) {
  128.     aut(r, result) cout << r << " ";
  129.     cout << endl;
  130. }
  131. bool comp(pair<ll, ll>p1, pair<ll, ll>p2) { return p1.second < p2.second; }
  132. bool isPrime(int n)
  133. {
  134.     // Corner cases 
  135.     if (n <= 1)  return false;
  136.     if (n <= 3)  return true;
  137.  
  138.     // This is checked so that we can skip  
  139.     // middle five numbers in below loop 
  140.     if (n % 2 == 0 || n % 3 == 0) return false;
  141.  
  142.     for (int i = 5; i * i <= n; i = i + 6)
  143.         if (n % i == 0 || n % (i + 2) == 0)
  144.             return false;
  145.  
  146.     return true;
  147. }
  148. ll power(ll a, ll b) {
  149.     if (a == 1)
  150.         return 1;
  151.     if (b == 0)
  152.         return 1;
  153.     ll c = power(a, b / 2);
  154.     ll res = 1;
  155.     if (b % 2) {
  156.         res = (c * c) % mod;
  157.         res *= a;
  158.         res %= mod;
  159.     }
  160.     else
  161.         res = ((c * c) % mod);
  162.     return res;
  163. }
  164. ll modInv(ll a) { return power(a, mod - 2) % mod; }
  165. ll fact[1], inv[1];
  166. void factorial(ll n) {
  167.     fact[0] = 1;
  168.     for (ll i = 1; i <= n; i++) {
  169.         fact[i] = fact[i - 1] * i;
  170.         fact[i] %= mod;
  171.     }
  172. }
  173. void InvFactorial(ll n) {
  174.     inv[0] = 1;
  175.     for (ll i = 1; i <= n; i++)
  176.         inv[i] = modInv(fact[i]);
  177. }
  178. ll ncr(ll n, ll r) {
  179.     if (n < r || n < 0 || r < 0)
  180.         return 0;
  181.     ll b = inv[n - r];
  182.     ll c = inv[r];
  183.     ll a = fact[n] * b;
  184.     a %= mod;
  185.     a *= c;
  186.     a %= mod;
  187.     return a;
  188. }
  189. //ifstream cin("b_read_on.txt"); ofstream cout("output3.txt");
  190. //Use (<<) for multiplication
  191. //Use (>>) for division
  192. //ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout<<fixed;cerr.tie(NULL);
  193. // find_by_order -> value at index
  194. // order_of_key -> index of value
  195. // while using (1<<i) use ((ll)1<<(ll)i) 
  196. // in Floyd-Warshall Algo, k is outer loop 
  197. // If an element was not initially in map and if asked mp[a],the element gets inserted 
  198. // a%=mod take a lot of time... try to use it minimum and use memset as it reduces a lot of time usage...use if(a>=mod) a%=mod
  199. //cout<<(double) can be harmful , always use printf(%.9llf)...take scanf("%lf",&p[i][j]) as input , not llf;
  200. //use s.erase(it++) for erasing iterator and then moving to the next one
  201. //never use adj.resize(n) as value is persistent, always erase
  202. //use __builtin_popcountll() for ll
  203. // no of prime numbers in range : (70,19) , (1000,168) , (100000,1229) , (sqrt(10^9),3409) ;
  204. //always check the use of segment tree using bottom-up dp
  205. /*
  206.    Try the solution
  207.  
  208.    10^8                              O(N) Border case
  209.    10^7                         O(N) Might be accepted
  210.    10^6                              O(N) Perfect
  211.    10^5                              O(N * logN)
  212.    10^3                              O(N ^ 2)
  213.    10^2                              O(N ^ 3)
  214.    10^9                              O(logN) or Sqrt(N)
  215.  
  216. */
  217. vi par(1000001, -1);
  218. vi ran(1000001, 1);
  219. int find(int a) {
  220.     if (par[a] < 0) return a;
  221.     return par[a] = find(par[a]);
  222. }
  223. void uni(int a, int b) {
  224.     if (ran[a] > ran[b]) {
  225.         par[b] = a;
  226.         ran[a] += ran[b];
  227.     }
  228.     else {
  229.         par[a] = b;
  230.         ran[b] += ran[a];
  231.     }
  232.  
  233.  
  234. }
  235.  
  236.  
  237. int main() {
  238.     ios_base::sync_with_stdio(false);
  239.     cin.tie(NULL);
  240.     cout.tie(NULL);
  241.     int test;
  242.     //test = 1;
  243.     cin >> test;
  244.  
  245.     while (test--) {
  246.         int n, e;
  247.         cin >> n >> e;
  248.         int flag = 0;
  249.         while (e--) {
  250.             int n1, n2;
  251.             string c;
  252.             cin >> n1 >> c >> n2;
  253.             n1 = find(n1);
  254.             n2 = find(n2);
  255.  
  256.             if (n1 == n2 && c == "!=") {
  257.                 flag = 1;
  258.             }
  259.             else if (n1 != n2 && c == "=") uni(n1, n2);
  260.  
  261.  
  262.  
  263.         }
  264.         if (flag ) cout << "NO" << endl;
  265.         else cout << "YES" << endl;
  266.  
  267.  
  268.     }
  269.  
  270. }
  271.  
  272.  
  273.  
  274.  
  275.  
  276.  
  277.  
  278.  
  279.  
  280.  
Runtime error #stdin #stdout 0s 11068KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/nJMHTH
language:
C++14 (gcc 8.3)
created:
3 years ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!