fork download
copy 
  1. //#pragma GCC optimize("Ofast,unroll-loops")
  2. //#pragma GCC target("avx2,tune=native")
  3. #include <bits/stdc++.h>
  4. using namespace std;
  5.  
  6. #define file "o"
  7. #define ff(i, a, b) for(auto i=(a); i<=(b); ++i)
  8. #define ffr(i, b, a) for(auto i=(b); i>=(a); --i)
  9. #define nl "\n"
  10. #define ss " "
  11. #define pb emplace_back
  12. #define fi first
  13. #define se second
  14. #define sz(s) (int)s.size()
  15. #define all(s) (s).begin(), (s).end()
  16. #define ms(a,x) memset(a, x, sizeof (a))
  17. #define cn continue
  18. #define re exit(0)
  19.  
  20. typedef long long ll;
  21. typedef unsigned long long ull;
  22. typedef long double ld;
  23. typedef vector<int> vi;
  24. typedef vector<ll> vll;
  25. typedef pair<int, int> pii;
  26. typedef pair<ll, ll> pll;
  27. typedef vector<pii> vpii;
  28. typedef vector<pll> vpll;
  29.  
  30. mt19937_64 rng(chrono::steady_clock::now().time_since_epoch().count());
  31. ll ran(ll l, ll r)
  32. {
  33.     return uniform_int_distribution<ll> (l, r)(rng);
  34. }
  35.  
  36. inline void rf()
  37. {
  38.     ios_base::sync_with_stdio(false);
  39.     cin.tie(nullptr); cout.tie(nullptr);
  40.     if(fopen(file".inp","r"))
  41.     {
  42.         freopen(file".inp","r",stdin);
  43.         freopen(file".out","w",stdout);
  44.     }
  45. }
  46.  
  47. const int mod=998244353;
  48. const int maxn=3e5+15;
  49. const ll inf=5e16;
  50.  
  51. template<typename T> inline void add(T &x, const T &y)
  52. {
  53.     x+=y;
  54.     if(x>=mod) x-=mod;
  55.     if(x<0) x+=mod;
  56. }
  57.  
  58. template<typename T> inline bool maxi(T &a, T b)
  59. {
  60.     if(a>=b) return 0;
  61.     a=b; return 1;
  62. }
  63.  
  64. template<typename T> inline bool mini(T &a, T b)
  65. {
  66.     if(a<=b) return 0;
  67.     a=b; return 1;
  68. }
  69.  
  70. struct Node
  71. {
  72.     unsigned char k;
  73.     unsigned char u[101];
  74.     unsigned char v[101];
  75. };
  76.  
  77. struct DSU
  78. {
  79.     int p[105], sz[105], comps;
  80.     void init(int n)
  81.     {
  82.         comps=n;
  83.         ff(i,1,n) p[i]=i, sz[i]=1;
  84.     }
  85.     int findp(int x)
  86.     {
  87.         if(p[x]==x) return x;
  88.         return p[x]=findp(p[x]);
  89.     }
  90.     bool unite(int a,int b)
  91.     {
  92.         a=findp(a); b=findp(b);
  93.         if(a==b) return 0;
  94.         if(sz[a]<sz[b]) swap(a,b);
  95.         p[b]=a;
  96.         sz[a]+=sz[b];
  97.         --comps;
  98.         return 1;
  99.     }
  100. };
  101.  
  102. int n,m,q;
  103. unsigned char ex[100005], ey[100005];
  104. Node st[400005];
  105.  
  106. Node mergeNode(const Node &A, const Node &B)
  107. {
  108.     DSU d;
  109.     d.init(n);
  110.     Node res;
  111.     res.k=0;
  112.     ff(i,0,(int)A.k-1)
  113.     {
  114.         if(d.unite(A.u[i],A.v[i]))
  115.         {
  116.             res.u[(int)res.k]=A.u[i];
  117.             res.v[(int)res.k]=A.v[i];
  118.             ++res.k;
  119.         }
  120.     }
  121.     ff(i,0,(int)B.k-1)
  122.     {
  123.         if(d.unite(B.u[i],B.v[i]))
  124.         {
  125.             res.u[(int)res.k]=B.u[i];
  126.             res.v[(int)res.k]=B.v[i];
  127.             ++res.k;
  128.         }
  129.     }
  130.     return res;
  131. }
  132.  
  133. void build(int id,int l,int r)
  134. {
  135.     if(l==r)
  136.     {
  137.         st[id].k=1;
  138.         st[id].u[0]=ex[l];
  139.         st[id].v[0]=ey[l];
  140.         return;
  141.     }
  142.     int mid=(l+r)>>1;
  143.     build(id<<1,l,mid);
  144.     build(id<<1|1,mid+1,r);
  145.     st[id]=mergeNode(st[id<<1],st[id<<1|1]);
  146. }
  147.  
  148. void getNodes(int id,int l,int r,int u,int v, vector<int> &vec)
  149. {
  150.     if(u>r || v<l) return;
  151.     if(u<=l && r<=v)
  152.     {
  153.         vec.pb(id);
  154.         return;
  155.     }
  156.     int mid=(l+r)>>1;
  157.     getNodes(id<<1,l,mid,u,v,vec);
  158.     getNodes(id<<1|1,mid+1,r,u,v,vec);
  159. }
  160.  
  161. signed main()
  162. {
  163.     rf();
  164.     cin>>n>>m;
  165.     ff(i,1,m)
  166.     {
  167.         int x,y;
  168.         cin>>x>>y;
  169.         ex[i]=(unsigned char)x;
  170.         ey[i]=(unsigned char)y;
  171.     }
  172.     build(1,1,m);
  173.     cin>>q;
  174.     while(q--)
  175.     {
  176.         int l,r;
  177.         cin>>l>>r;
  178.         vector<int> nodes;
  179.         nodes.reserve(32);
  180.         getNodes(1,1,m,l,r,nodes);
  181.         DSU d;
  182.         d.init(n);
  183.         for(int id:nodes)
  184.         {
  185.             Node &cur=st[id];
  186.             ff(i,0,(int)cur.k-1)
  187.                 d.unite(cur.u[i],cur.v[i]);
  188.         }
  189.         if(d.comps==1) cout<<"Yes"<<nl;
  190.         else cout<<"No"<<nl;
  191.     }
  192. }
  193.  
Success #stdin #stdout 0.01s 5320KB
comments (?)
stdin
copy 
4 6
1 2
2 3
3 4
4 1
1 3
2 3
2
1 3
3 5
stdout
copy 
Yes
No
https://ideone.com/HfY6y5
language:
C++14 (gcc 8.3)
created:
5 days 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!