Guest User

Memroy_limit

a guest
Dec 27th, 2019
157
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 1.51 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.     vis[a] = 1;
  38.  
  39.     for(int i = 0;i<g[a].size();i++) {
  40.         if (!vis[g[a][i]]) {
  41.             dfs(g[a][i]);
  42.         }
  43.     }
  44. }
  45.  
  46. int32_t main() {
  47.     int n;
  48.     std::vector<pair<pair<int,int>,int>> ranges;
  49.     cin>>n;
  50.     fori(i,n) {
  51.         int x,y;
  52.         cin>>x>>y;
  53.         ranges.pb(mp(mp(x,y),i));
  54.     }
  55.     set<pair<int,int>> s;
  56.     srt(ranges);
  57.  
  58.     fori(i,n) {
  59.         auto it = s.lower_bound(mp(ranges[i].F.F,0));
  60.        
  61.         while (it != s.end() && it->F < ranges[i].F.S) {
  62.             g[ranges[i].S].pb(it->S);
  63.             g[it->S].pb(ranges[i].S);
  64.             // cout<<endl<<it->S<<"   "<<ranges[i].S<<"   an edge";
  65.             it++;
  66.         }
  67.         s.insert(mp(ranges[i].F.S,ranges[i].S));
  68.     }
  69.     ranges.clear();
  70.     s.clear();
  71.  
  72.     fori(i,n) {
  73.         edges += g[i].size();
  74.         if(!vis[i]) {
  75.             dfs(i);
  76.             con++;
  77.         }
  78.     }
  79.  
  80.     if (edges/2 == n-1 && con == 1) {
  81.         cout<<"YES";
  82.     } else {
  83.         cout<<"NO";
  84.     }
  85.     // cout<<"\n"<<edges<<"   "<<con;
  86.  
  87. }
Add Comment
Please, Sign In to add comment