fork download
copy 
  1. #include <bits/stdc++.h>
  2. #include <ext/pb_ds/assoc_container.hpp>
  3. #include <ext/pb_ds/tree_policy.hpp>
  4.  
  5. using namespace std;
  6. using namespace __gnu_pbds;
  7. using ll = long long;
  8. using ld = long double;
  9.  
  10. #define all(x)  x.begin(),x.end()
  11. #define v(x) vector<x>
  12. #define nl '\n'
  13. #define fxd(x) fixed << setprecision(x)
  14. template<class t> using ordered_set = tree<t, null_type, less<t>, rb_tree_tag, tree_order_statistics_node_update>;
  15. template<class t> using ordered_multiset = tree<t, null_type, less_equal<t>, rb_tree_tag, tree_order_statistics_node_update>;
  16. vector<pair<ll,ll>> prs;
  17. int n , m;
  18. /* 
  19.  function that takes x and y and check if in every pair atleast one element equal x or y if yes it returns -1 
  20.  if no and and in a pair this condions dosn't hold then it returns the index of the pair that breaks the condition
  21.  */
  22. ll check(ll x , ll y)
  23. {
  24.     for (int i = 0; i < m; i++)
  25.     {
  26.         // note that i search if there's any problem found here if yes i return the index of the pair that is nigga
  27.         if(!(x == prs[i].first || x == prs[i].second || y == prs[i].first || y == prs[i].second)) return i;
  28.     }
  29.     // this happen when every pair is ok with this x and y (allhamdullah);
  30.     return -1;
  31. }
  32.  
  33. int main()
  34. {
  35.     ios_base::sync_with_stdio(false); cin.tie(nullptr); cout.tie(nullptr);
  36.     //just take the input stuff
  37.     cin >> n >> m;
  38.     prs.resize(m);
  39.     for (int i = 0; i < m; i++)
  40.     {
  41.         cin >> prs[i].first >> prs[i].second;
  42.     }
  43.  
  44.  
  45.     ll stat; // this store if the current x and y work or not
  46.     ll fail; // this stores the index that have a problem with current x 
  47.  
  48.  
  49.     stat = check(prs[0].first,-1); // we try the first element in the first pair note that i put y = -1 because it's ganted that the values will not equal -1
  50.     if(stat == -1)
  51.     {
  52.         // dame bro the first element of the first pair works on it's own this good
  53.         cout << "YES";
  54.         return 0;
  55.     }
  56.     else
  57.     {
  58.         // ok now the first elemnt of the first index faild so we will try to take y from the first
  59.         fail = stat;
  60.         stat = check(prs[0].first,prs[fail].first);
  61.         if(stat == -1)
  62.         {
  63.             cout << "YES";
  64.             return 0;
  65.         }
  66.         else
  67.         {
  68.             // ok the first element of the faild pair also falid to be the y so we try the second one
  69.             stat = check(prs[0].first,prs[fail].second);
  70.             if(stat == -1)
  71.             {
  72.                 cout << "YES";
  73.                 return 0;
  74.             }
  75.         }
  76.     }
  77.  
  78.     // now we lowkey now that the first element of the first piar dosen't work to be our x (ab3d allah 3nkm al exat) so we try the secend element of the first pair to be the x
  79.     stat = check(prs[0].second,-1);
  80.     if(stat == -1)
  81.     {
  82.         // the seconde element can work on it's own 
  83.         cout << "YES";
  84.         return 0;
  85.     }
  86.     // we try the same shit again
  87.     else
  88.     {
  89.         fail = stat;
  90.         stat = check(prs[0].second,prs[fail].first);
  91.         if(stat == -1)
  92.         {
  93.             cout << "YES";
  94.             return 0;
  95.         }
  96.         else
  97.         {
  98.             stat = check(prs[0].second,prs[fail].second);
  99.             if(stat == -1)
  100.             {
  101.                 cout << "YES";
  102.                 return 0;
  103.             }
  104.         }
  105.     }
  106.     // so now we know that we cant use any elements in the first pair so ofc there's no solution
  107.     cout << "NO";
  108.     return 0;
  109. }
Success #stdin #stdout 0.01s 5280KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
YES
https://ideone.com/NBHpDy
language:
C++14 (gcc 8.3)
created:
1 hour ago
visibility:
public

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!