Guest User

Memory

a guest
Dec 27th, 2019
154
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.64 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3. #define fori(i,n) for(int i =0;i<n;i++)
  4. #define pb push_back
  5. #define ll long long
  6. #define int long long
  7. #define F first
  8. #define S second
  9. #define mp make_pair
  10. #define rev(a) reverse(a.begin(),a.end())
  11. #define srt(a) sort(a.begin(),a.end())
  12. #define FAST ios_base::sync_with_stdio(false);cin.tie(NULL);cout.tie(NULL);cout.precision(15);
  13.  
  14.  
  15. int mod = 1000000007;
  16.  
  17. int pow(int a, int b) {
  18.     int ans = 1;
  19.     a %= mod;
  20.     while(b) {
  21.         if(b%2) {
  22.             ans *= a;
  23.             ans %= mod;
  24.         }
  25.         b /= 2;
  26.         a *= a;
  27.         a %= mod;
  28.     }
  29.     return ans;
  30. }
  31.  
  32. std::vector<int> g[500005];
  33. bool vis[500005];
  34. int con=0,edges=0;
  35.  
  36. void dfs(int a) {
  37.     stack<int> stc;
  38.     stc.push(a);
  39.  
  40.     while(!stc.empty()) {
  41.         int t = stc.top();
  42.         stc.pop();
  43.         vis[t] = 1;
  44.         for(int i = 0;i<g[t].size();i++) {
  45.             if (!vis[g[t][i]]) {
  46.                 vis[g[t][i]] = 1;
  47.                 stc.push(g[t][i]);
  48.             }
  49.         }
  50.     }
  51. }
  52.  
  53. int32_t main() {
  54.     int n;
  55.     std::vector<pair<pair<int,int>,int>> ranges;
  56.     cin>>n;
  57.     fori(i,n) {
  58.         int x,y;
  59.         cin>>x>>y;
  60.         ranges.pb(mp(mp(x,y),i));
  61.     }
  62.     set<pair<int,int>> s;
  63.     srt(ranges);
  64.  
  65.     fori(i,n) {
  66.         auto it = s.lower_bound(mp(ranges[i].F.F,0));
  67.        
  68.         while (it != s.end() && it->F < ranges[i].F.S) {
  69.             g[ranges[i].S].pb(it->S);
  70.             g[it->S].pb(ranges[i].S);
  71.             // cout<<endl<<it->S<<"   "<<ranges[i].S<<"   an edge";
  72.             it++;
  73.         }
  74.         s.insert(mp(ranges[i].F.S,ranges[i].S));
  75.     }
  76.     ranges.clear();
  77.     s.clear();
  78.  
  79.     fori(i,n) {
  80.         edges += g[i].size();
  81.         if(!vis[i]) {
  82.             dfs(i);
  83.             con++;
  84.         }
  85.     }
  86.  
  87.     if (edges/2 == n-1 && con == 1) {
  88.         cout<<"YES";
  89.     } else {
  90.         cout<<"NO";
  91.     }
  92.     // cout<<"\n"<<edges<<"   "<<con;
  93.  
  94. }
Add Comment
Please, Sign In to add comment