提出 #42099268

---

ソースコード 拡げる

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
#define rep(i,a,n) for (int i=a;i<(int)(n);i++)
#define per(i,a,n) for (int i=n;i-->(int)(a);)
ll read(){ll r;scanf("%lld",&r);return r;}

class UnionFind{
  public:
    unordered_map<int,int> f;
    unordered_map<int,int> cnt;
    UnionFind(int sz){ // 0-index
      f=unordered_map<int,int>();
      rep(i,0,sz) f[i]=i;
      rep(i,0,sz) cnt[i]=1;
    }
    UnionFind(const unordered_map<int,int>&part){ // 0-index, 部分拷贝, 只留根
      f=part;
      cnt = unordered_map<int,int>();
      for(auto [k,_]:f) cnt[k] = 1;
    }
    int root(int u){ return f[u]==u?u:f[u]=root(f[u]); }
    void link(int u,int v){
      int fu=root(u);
      int fv=root(v);
      if(fu == fv) return ;
      if(cnt[fu] > cnt[fv]){
        f[fv] = fu;
        cnt[fu] += cnt[fv];
      }else{
        f[fu] = fv;
        cnt[fv] += cnt[fu];
      }
    }
};

vector<array<int,2> > edge; // u,v
vector<array<int,3> > eid2q[200010]; // s,t,qid
vector<int> ans;

void addEdge(const vector<int>&eids,int l,int r,UnionFind&uf){
  rep(i,l,r) {
    auto [u,v] = edge[eids[i]];
    uf.link(u,v);
  }
}

// [l,r)
void solve(const vector<int>&eids,int l,int r,const UnionFind&_uf){
  int sz = r-l;
  if(sz == 1){
    auto uf=_uf;
    int eid=eids[l];
    auto [u,v] = edge[eid];
    int fu=uf.root(u);
    int fv=uf.root(v);
    if(fu==fv) return ;
    for(auto [s,t,qid]:eid2q[eid]) {
      int fs = uf.root(s);
      int ft = uf.root(t);
      if(fs != ft and (
           (fs == fu and ft == fv) or
           (fs == fv and ft == fu)
           )){
        ans[qid] = true;
      }
    }
    return ;
  }
  auto ufr = _uf;
  addEdge(eids,l     ,l+sz/2,ufr);
  solve  (eids,l+sz/2,r     ,ufr);

  auto ufl = _uf;
  addEdge(eids,l+sz/2,r     ,ufl);
  solve  (eids,l     ,l+sz/2,ufl);
}

int main(){
  int n=read();
  int m=read();
  vector< vector<int> > w2eid(m+1); // weight 2 eid
  rep(i,0,m){
    int u=read()-1;
    int v=read()-1;
    int w=read();
    w2eid[w].push_back(i);
    edge.push_back({u,v});
  }
  int q=read();
  rep(i,0,q){
    int eid=read()-1;
    int s=read()-1;
    int t=read()-1;
    eid2q[eid].push_back({s,t,i});
  }
  ans = vector<int>(q);
  UnionFind uf(n);
  rep(w,1,m+1) if(w2eid[w].size()) {
    unordered_map<int,int> sub; // 部分拷贝的并查集
    auto add=[&](int u){ if(!sub.count(u)) { // 只加根
      assert(u == uf.f[u]);
      sub[u] = uf.f[u];
    } };

    for(auto eid:w2eid[w]){
      auto &[u,v]=edge[eid];
      u = uf.root(u);
      add(u);
      v = uf.root(v);
      add(v);
    }
    for(auto eid:w2eid[w]){
      per(i,0,size(eid2q[eid])) {
        auto &[s,t,qid] = eid2q[eid][i];
        s = uf.root(s);
        t = uf.root(t);
        if(!sub.count(s) or !sub.count(t)){ // 有不涉及的点，那么连完依然不涉及, 直接忽略
          swap(eid2q[eid][i],eid2q[eid].back());
          eid2q[eid].pop_back();
        }
      }
    }
    solve(w2eid[w],0,size(w2eid[w]), UnionFind(sub));
    addEdge(w2eid[w],0,size(w2eid[w]), uf);
  }
  for(auto o:ans) printf("%d\n",o);
  return 0;
}

提出情報

コンパイルエラー

./Main.cpp: In function ‘ll read()’:
./Main.cpp:7:21: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
    7 | ll read(){ll r;scanf("%lld",&r);return r;}
      |                ~~~~~^~~~~~~~~~~

ジャッジ結果