fork download
copy 
  1. #include <bits/stdc++.h>
  2. #define ll long long
  3. #define sti string
  4. #define bit(n,i) ((n>>i) &1)
  5. #define itachi ios_base::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  6. #define maxn 2000005
  7. #define fi first
  8. #define se second
  9.  
  10.  
  11. using namespace std;
  12.  
  13. struct Query {
  14.    int l,r,id;
  15.    bool operator < (const Query &other) const {
  16.       return r < other.r;
  17.    }
  18. };
  19.  
  20. int q;
  21. vector<Query> que;
  22. const int block=250;
  23. int n,m;
  24. int u[maxn],v[maxn];
  25. int ans[maxn];
  26.  
  27. struct DSU {
  28.    int n;
  29.    vector<int> sz,par;
  30.    vector<pair<int,int>> stk;
  31.    int comp;
  32.  
  33.    DSU(int _n=0){
  34.        n=_n;
  35.        sz.assign(n+5,0);
  36.        par.assign(n+5,0);
  37.    }
  38.    void reset(){
  39.       stk.clear();
  40.       comp=n;
  41.       for(int i=1;i<=n;i++){
  42.         sz[i]=1;
  43.         par[i]=i;
  44.       }
  45.    }
  46.    int find_par(int u){
  47.       return (par[u]==u ? u : find_par(par[u]));
  48.    }
  49.    void join(int u,int v){
  50.      u=find_par(u);
  51.      v=find_par(v);
  52.      if(u==v) {
  53.         stk.push_back({-1,-1});
  54.         return ;
  55.      }
  56.      if(sz[u] < sz[v]) swap(u,v);
  57.      stk.push_back({v,sz[u]});
  58.      par[v]=u;
  59.      sz[u]+=sz[v];
  60.      comp--;
  61.    }
  62.    int roll(){
  63.      return stk.size();
  64.    }
  65.  
  66.    void rollback(int Time){
  67.      while(stk.size() > Time){
  68.         pair<int,int> top=stk.back();
  69.         int v=top.fi;
  70.         int Size=top.se;
  71.         stk.pop_back();
  72.         if(v==-1) continue;
  73.         int u=par[v];
  74.         sz[u]=Size;
  75.         par[v]=v;
  76.         comp++;
  77.      }
  78.    }
  79. };
  80.  
  81.  
  82. int main()
  83. {
  84.     itachi
  85.     //freopen("graph.inp","r",stdin);
  86.     //freopen("graph.out","w",stdout);
  87.     cin>>n>>m;
  88.     for(int i=1;i<=m;i++){
  89.         cin>>u[i]>>v[i];
  90.     }
  91.     cin>>q;
  92.     for(int i=0;i<q;i++){
  93.         int l,r;
  94.         cin>>l>>r;
  95.         que.push_back({l,r,i});
  96.     }
  97.     vector<vector<Query>> blocks((m+block-1)/block);
  98.     for(auto &tmp : que){
  99.         blocks[(tmp.l-1)/block].push_back(tmp);
  100.     }
  101.     DSU dsu(n);
  102.     for(auto &vec : blocks){
  103.         if(vec.empty()) continue;
  104.         sort(vec.begin(),vec.end());
  105.         int L=vec[0].l;
  106.         int blockR = min((L-1)/block*block + block, m);
  107.         int R = blockR;
  108.         dsu.reset();
  109.         for(auto &tmp : vec){
  110.             while(R < tmp.r){
  111.                 R++;
  112.                 dsu.join(u[R],v[R]);
  113.             }
  114.             int turn=dsu.roll();
  115.             for(int i=tmp.l;i<=blockR;i++){
  116.                 dsu.join(u[i],v[i]);
  117.             }
  118.             ans[tmp.id]=(dsu.comp==1);
  119.             dsu.rollback(turn);
  120.         }
  121.     }
  122.     for(int i=0;i<q;i++) cout<<(ans[i] ? "Yes" : "No")<<'\n';
  123.     return 0;
  124. }
  125.  
Success #stdin #stdout 0.01s 5288KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
Standard output is empty
https://ideone.com/P7PTRZ
language:
C++14 (gcc 8.3)
created:
3 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!