提出 #42102172

---

ソースコード 拡げる

#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:
    vector<int> f; // f[i]
    UnionFind(int sz){ // 0-index
      f.resize(sz);
      iota(begin(f),end(f),0);
    }
    int leader(int u) { return f[u] == u ? u :f[u] = leader(f[u]); }
    void merge(int u,int v) { f[leader(u)] = leader(v); }
    bool same(int u,int v) {return leader(u) == leader(v);}
};

class lowlink {
  int n;
  vector<vector<pair<int, int>>> G;
  vector<int> in, out, low;
  unordered_map<int, int> bridge; // bridge[eid] = child vertex

  void dfs(int u, int p, int &ti) { // 计算所有low,和找桥
    in[u] = low[u] = ti++;
    for (auto [v, id]: G[u]) {
      if (in[v] == -1) {
        dfs(v, id, ti);
        low[u] = min(low[u], low[v]);
        if (low[v] > in[u]) bridge[id] = v;
      } else if (id != p) {
        low[u] = min(low[u], in[v]);
      }
    }
    out[u] = ti;
  }

  void init() {
    n = G.size();
    in.assign(n, -1);
    out.assign(n, -1);
    low.assign(n, -1);
    int ti = 0;
    rep(i,0,n) if (in[i] == -1) dfs(i, -1, ti);
  }

  public:
  lowlink(const vector<vector<pair<int, int>>> &G) : G(G) { init(); }

  bool query(int a, int s, int t) { // a是桥 且 s,t有且只有一个在 桥子节点的子(树/图)中
    assert(0 <= s and s < n);
    assert(0 <= t and t < n);
    assert(s != t);
    if (!bridge.count(a)) return false;
    int l = in[bridge[a]];
    int r = out[bridge[a]];
    s = in[s];
    t = in[t];
    return (l <= s and s < r) xor (l <= t and t < r);
  }
};

int main() {
  int n=read();
  int m=read();
  vector<int> u(m), v(m);
  vector<vector<int>> w2e(m); //
  rep(i,0,m){
    u[i]=read()-1;
    v[i]=read()-1;
    w2e[read()-1].push_back(i);
  }
  int q=read();
  vector< vector<array<int,3> > > e2stq(m);
  rep(i,0,q) {
    int eid=read()-1;
    int s  =read()-1;
    int t  =read()-1;
    e2stq[eid].push_back({s,t,i});
  }
  vector<int> ans(q, -1);
  UnionFind uf(n);
  rep(w,0,m) { // 先处理 一定不可能0
    for(int eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if (uf.same(s, t)) ans[qid] = 0;
    for(int eid:w2e[w]) uf.merge(u[eid], v[eid]);
    for(int eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if (!uf.same(s, t)) ans[qid] = 0;
  }

  uf = UnionFind(n);
  rep(w,0,m){
    // 离散化 构建小图
    vector<int> ls;
    for (int eid: w2e[w]) {
      ls.push_back(uf.leader(u[eid]));
      ls.push_back(uf.leader(v[eid]));
    }
    sort(ls.begin(), ls.end());
    ls.erase(unique(ls.begin(), ls.end()), ls.end());
    auto lb=[&](int u)->int{ return lower_bound(ls.begin(), ls.end(), uf.leader(u)) - ls.begin();};

    int sz = ls.size();
    vector<vector<pair<int, int>>> G(sz); // G[u] = array {v, edgeid}
    for (int eid: w2e[w]) if(u[eid] != v[eid]){
      int nu = lb(u[eid]);
      int nv = lb(v[eid]);
      G[nu].emplace_back(nv, eid);
      G[nv].emplace_back(nu, eid);
    }
    lowlink lk(G); // 每次构建 <= 2边, 总代价小于等于O(2m)
    for(auto eid:w2e[w]) for(auto [s,t,qid]:e2stq[eid]) if(ans[qid] == -1) {
      int ns = lb(s);
      int nt = lb(t);
      assert(ns != nt);
      assert(ns < sz and nt < sz);
      assert(ls[ns] == uf.leader(s) and ls[nt] == uf.leader(t));
      // 已经保证了 加了=w的 所有边 s,t会连通, 只需要查询eid能否让它们断开
      ans[qid] = lk.query(eid, ns, nt);
    }
    for (int eid: w2e[w]) uf.merge(u[eid], v[eid]);
  }
  rep(i,0,q) printf("%d\n", ans[i]);
  return 0;
}

提出情報

コンパイルエラー

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

ジャッジ結果