codeforces 892E 可撤销并查集

https://codeforces.com/problemset/problem/892/E

把询问离线,分步回答.

#include
#define ll long long
#define rep(ii,a,b) for(int ii=a;ii<=b;++ii)
#define per(ii,a,b) for(int ii=b;ii>=a;--ii)
#define forn(i,x,g,e) for(int i=g[x];i;i=e[i].next)
#define IO ios::sync_with_stdio(false);cin.tie(0);cout.tie(0)
#define ull unsigned long long
#define fi first
#define se second
#define mp make_pair
#define pii pair
#define all(x) x.begin(),x.end()
#define show(x) cout<<#x<<"="< stk;
  void init(int tot){
    rep(i,1,tot) fa[i]=i,sz[i]=1;
  }
  int find(int now){
    if(fa[now]==now) return now;
    return find(fa[now]);
  }
  bool unite(int a,int b){
    a=find(a),b=find(b);
    if(a==b)return 0;
    if(sz[a]a[maxn];
bool cmp(int a,int b){return e[a].cost b[maxn],q[maxn];
int ans[maxn];
bool check(int id,int from,int to){
  bool res=1;
  int sum=0;
  rep(i,from,to){
    if(dsu.unite(e[q[id][i]].from,e[q[id][i]].to)) ++sum;
    else res=0;
  }
  rep(i,1,sum) dsu.undo();
  return res;
}
int main() {IO;
  cin>>n>>m;
  rep(i,1,m) {
    cin>>e[i].from>>e[i].to>>e[i].cost;
    b[e[i].cost].push_back(i);
  }
  cin>>k;
  rep(i,1,k){
    int sz;cin>>sz;
    rep(_,1,sz){
      int x;cin>>x;
      q[i].push_back(x);
    }
    sort(all(q[i]),cmp);
    int from=0;
    rep(j,1,sz-1)
      if(e[q[i][j]].cost!=e[q[i][j-1]].cost){
        a[e[q[i][j-1]].cost].push_back({i,from,j-1,0});
        from=j;
      }
    a[e[q[i][sz-1]].cost].push_back({i,from,sz-1,0});
  }
  dsu.init(n);
  rep(i,1,maxn-5){
    for(node j:a[i]) 
      if(!check(j.id,j.from,j.to))
        ans[j.id]=1;
    for(int j:b[i])
      dsu.unite(e[j].from,e[j].to);
  }
  rep(i,1,k) if(ans[i])cout<<"NO\n";
  else cout<<"YES\n";
  return 0;
}