Submission #8085133

---

Source Code Expand

#pragma GCC optimize ("O3")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")

#include <bits/stdc++.h>
using namespace std;
using Int = long long;
typedef pair<int,int> P; typedef pair<Int,Int> Pl;
const int mod = 1e9+7;
const Int Inf = 1e17;
#define END {cout<<ans<<'\n'; return 0;}
#define ALL(v) (v).begin(),(v).end()
#define fi first
#define se second
#define mp make_pair
#define Pr(t) priority_queue<t>
#define gPr(t) priority_queue<t,vector<t>,greater<t>>
#define V(t) vector<t>
#define rep(i,n) for(int(i)=0; i<n; i++)
#define rer(i,l,r) for(int i=l; i<=r; i++)
#define gnr(i,l,r) for(int i=r; i>=l; i--)
#define eb emplace_back
#define pri1(a) cout<<(a)<<'\n'
#define pri2(a,n) {rep(pri2i,n-1)cout<<a[pri2i]<<' '; cout<<a[n-1]<<'\n';}
#define prip(p) cout<<p.fi<<' '<<p.se<<'\n'
template<class T> inline bool cmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool cmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

int n,m,_,x,y,q;
string s,sb;
bool ok;
char cf,cb;

struct PartiallyPersistentUnionFind{
  vector<int> time, par;
  vector<vector<pair<int,int>>> size;
  int now = 0;
 
  PartiallyPersistentUnionFind(int siz){
    time.assign(siz, 1e9);
    par.assign(siz, 1);
    size.assign(siz, vector<pair<int,int>>(1,{0,1}));
  }

  int find(int t,int x){
    if(time[x] > t)return x;
    else return find(t, par[x]);
  }

  int unite(int x, int y){
    ++now;
    x = find(now, x), y = find(now, y);
    if(x == y) return now;
    if(par[y] > par[x]) swap(x, y);
    par[x] += par[y];
    par[y] = x;
    time[y] = now;
    size[x].push_back({now, par[x]});
    return now;
  }

  bool same(int t,int x,int y){
    return find(t, x) == find(t, y);
  }
 
  int parsize(int t,int x){
    int be = 0, en = now+1, mid;
    while(be - en > 1){
      mid = (be + en) / 2;
      if(size[x][now].first < t)en = mid;
      else be = mid;
    }
    return size[x][en].second;
  }
};

int main(){
  cin.tie(nullptr); ios::sync_with_stdio(0);

  cin>>n>>m; PartiallyPersistentUnionFind a(n);
  rep(i,m){
    cin>>x>>y;
    a.unite(x-1,y-1);
  }
  cin>>q;
  rep(i,q){
    cin>>x>>y; x--; y--;
    int ng=0,ok=m+1;
    while(ok-ng>1){
      int mid=(ok+ng)/2;
      if(a.same(mid,x,y))ok=mid;
      else ng=mid;
    }
    pri1(ok==m+1?-1:ok);
  }
}

Submission Info

Judge Result