#936338 (C++17) No.922 東北きりきざむたん

提出ソース
結果

問題	No.922 東北きりきざむたん
ユーザー	miyo2580
提出日時	2023-12-04 22:50:59
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	250 ms / 2,000 ms
コード長	9,624 bytes
コンパイル時間	3,347 ms
コンパイル使用メモリ	233,712 KB
最終ジャッジ日時	2025-02-18 07:17:48
ジャッジサーバーID （参考情報）	judge4 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 4
other	AC * 26
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>
using namespace std;
#define repd(i,a,b) for (ll i=(a);i<(b);i++)
#define rep(i,n) repd(i,0,n)
#define all(x) (x).begin(),(x).end()
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return true; } return false; }
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return true; } return false; }
typedef long long ll;
typedef pair<ll,ll> P;
typedef vector<ll> vec;
using Graph = vector<vector<ll>>;
const long long INF = 1LL<<60;
const long long MOD = 1000000007;

//https://nyaannyaan.github.io/library/graph/graph-template.hpp
template <typename T>
struct edge {
  int src, to;
  T cost;

  edge(int _to, T _cost) : src(-1), to(_to), cost(_cost) {}
  edge(int _src, int _to, T _cost) : src(_src), to(_to), cost(_cost) {}

  edge &operator=(const int &x) {
    to = x;
    return *this;
  }

  operator int() const { return to; }
};
template <typename T>
using Edges = vector<edge<T>>;
template <typename T>
using WeightedGraph = vector<Edges<T>>;
using UnweightedGraph = vector<vector<int>>;

// Input of (Unweighted) Graph
UnweightedGraph graph(int N, int M = -1, bool is_directed = false,
                      bool is_1origin = true) {
  UnweightedGraph g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    if (is_1origin) x--, y--;
    g[x].push_back(y);
    if (!is_directed) g[y].push_back(x);
  }
  return g;
}

// Input of Weighted Graph
template <typename T>
WeightedGraph<T> wgraph(int N, int M = -1, bool is_directed = false,
                        bool is_1origin = true) {
  WeightedGraph<T> g(N);
  if (M == -1) M = N - 1;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    cin >> c;
    if (is_1origin) x--, y--;
    g[x].emplace_back(x, y, c);
    if (!is_directed) g[y].emplace_back(y, x, c);
  }
  return g;
}

// Input of Edges
template <typename T>
Edges<T> esgraph(int N, int M, int is_weighted = true, bool is_1origin = true) {
  Edges<T> es;
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    es.emplace_back(x, y, c);
  }
  return es;
}

// Input of Adjacency Matrix
template <typename T>
vector<vector<T>> adjgraph(int N, int M, T INF, int is_weighted = true,
                           bool is_directed = false, bool is_1origin = true) {
  vector<vector<T>> d(N, vector<T>(N, INF));
  for (int _ = 0; _ < M; _++) {
    int x, y;
    cin >> x >> y;
    T c;
    if (is_weighted)
      cin >> c;
    else
      c = 1;
    if (is_1origin) x--, y--;
    d[x][y] = c;
    if (!is_directed) d[y][x] = c;
  }
  return d;
}

/**
 * @brief グラフテンプレート
 * @docs docs/graph/graph-template.md
 */

//https://nyaannyaan.github.io/library/tree/rerooting.hpp

// Rerooting
// f1(c1, c2) ... merge value of child node
// f2(memo[i], chd, par) ... return value from child node to parent node
// memo[i] ... result of subtree rooted i
// dp[i] ... result of tree rooted i
template <typename T, typename G, typename F1, typename F2>
struct Rerooting {
  const G &g;
  const F1 f1;
  const F2 f2;
  vector<T> memo, dp;
  T I;

  Rerooting(const G &_g, const F1 _f1, const F2 _f2, const T &I_)
      : g(_g), f1(_f1), f2(_f2), memo(g.size(), I_), dp(g.size(), I_), I(I_) {
    dfs(0, -1);
    efs(0, -1, I);
  }

  const T &operator[](int i) const { return dp[i]; }

  void dfs(int cur, int par) {
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      dfs(dst, cur);
      memo[cur] = f1(memo[cur], f2(memo[dst], dst, cur));
    }
  }

  void efs(int cur, int par, const T &pval) {
    // get cumulative sum
    vector<T> buf;
    for (auto dst : g[cur]) {
      if (dst == par) continue;
      buf.push_back(f2(memo[dst], dst, cur));
    }
    vector<T> head(buf.size() + 1), tail(buf.size() + 1);
    head[0] = tail[buf.size()] = I;
    for (int i = 0; i < (int)buf.size(); i++) head[i + 1] = f1(head[i], buf[i]);
    for (int i = (int)buf.size() - 1; i >= 0; i--)
      tail[i] = f1(tail[i + 1], buf[i]);

    // update
    dp[cur] = par == -1 ? head.back() : f1(pval, head.back());

    // propagate
    int idx = 0;
    for (auto &dst : g[cur]) {
      if (dst == par) continue;
      efs(dst, cur, f2(f1(pval, f1(head[idx], tail[idx + 1])), cur, dst));
      idx++;
    }
  }
};

/**
 * @brief Rerooting(全方位木DP)
 * @docs docs/tree/rerooting.md
 */

struct UnionFind {
    vector<int> par; // par[i]:iの親の番号　(例) par[3] = 2 : 3の親が2

    UnionFind(int N = 0) : par(N, -1) {} //最初は全てが根であるとして初期化

    int root(int x) { // データxが属する木の根を再帰で得る：root(x) = {xの木の根}
        if (par[x] < 0) return x;
        return par[x] = root(par[x]);
    }

    bool unite(int x, int y) { // xとyの木を併合
        x = root(x); //xの根をrx
        y = root(y); //yの根をry
        if (x == y) return false; //xとyの根が同じ(=同じ木にある)時はそのまま
        if (par[x] > par[y])swap(x, y);//xとyの根が同じでない(=同じ木にない)時：xの根rxをyの根ryにつける
        par[x] += par[y];
        par[y] = x;
        return true;
    }

    bool same(int x, int y) { // 2つのデータx, yが属する木が同じならtrueを返す
        int rx = root(x);
        int ry = root(y);
        return rx == ry;
    }
    int size(int x) {
        return -par[root(x)];
    }
};

/* LCA(G, root): 木 G に対する根を root として Lowest Common Ancestor を求める構造体
    query(u,v): u と v の LCA を求める。計算量 O(logn)
    前処理: O(nlogn)時間, O(nlogn)空間
*/
struct LCA {
    vector<vector<int>> parent;  // parent[k][u]:= u の 2^k 先の親
    vector<int> dist;            // root からの距離
    LCA(const Graph& G, int root) { init(G, root); }

    // 初期化
    void init(const Graph& G, int root) {
        int V = G.size();
        int K = 1;
        while ((1 << K) < V) K++; //KはK>=log2(V)を満たす最小の整数
        parent.assign(K, vector<int>(V, -1));
        dist.assign(V, -1);
        dfs(G, root, -1, 0);
        for (int k = 0; k + 1 < K; k++) {
            for (int v = 0; v < V; v++) {
                if (parent[k][v] < 0) {
                    parent[k + 1][v] = -1;
                }
                else {
                    parent[k + 1][v] = parent[k][parent[k][v]];
                }
            }
        }
    }

    // 根からの距離と1つ先の頂点を求める
    void dfs(const Graph& G, int v, int p, int d) {
        parent[0][v] = p;
        dist[v] = d;
        for (auto e : G[v]) {
            if (e!= p) dfs(G, e, v, d + 1);
        }
    }

    int query(int u, int v) {
        if (dist[u] < dist[v]) swap(u, v);  // u の方が深いとする
        int K = parent.size();
        // LCA までの距離を同じにする
        for (int k = 0; k < K; k++) {
            if ((dist[u] - dist[v]) >> k & 1) {
                u = parent[k][u];
            }
        }
        // 二分探索で LCA を求める
        if (u == v) return u;
        for (int k = K - 1; k >= 0; k--) {
            if (parent[k][u] != parent[k][v]) {
                u = parent[k][u];
                v = parent[k][v];
            }
        }
        return parent[0][u];
    }
};

template <typename T>
vector<T> compress(vector<T> &X) {
    // ソートした結果を vals に
    vector<T> vals = X;
    sort(vals.begin(), vals.end());
    // 隣り合う重複を削除(unique), 末端のゴミを削除(erase)
    vals.erase(unique(vals.begin(), vals.end()), vals.end());
    // 各要素ごとに二分探索で位置を求める
    for (int i = 0; i < (int)X.size(); i++) {
        X[i] = lower_bound(vals.begin(), vals.end(), X[i]) - vals.begin();
    }
    return vals;
}

int main()
{  
    ios::sync_with_stdio(false);
    cin.tie(0);
    ll n,m,q;
    cin>>n>>m>>q;
    UnionFind t(n);
    vector<P> memo(m);
    rep(i,m){
      ll a,b;
      cin>>a>>b;
      a--;b--;
      memo[i]={a,b};
      t.unite(a,b);
    }
    map<ll,vector<P>> mp;
    rep(i,m){
      auto[x,y]=memo[i];
      mp[t.root(x)].push_back({x,y});
    }
    map<ll,vector<P>> mp2;
    vec cnt(n);
    rep(i,q){
      ll a,b;
      cin>>a>>b;
      a--;b--;
      if(t.same(a,b))mp2[t.root(a)].push_back({a,b});
      else{
        cnt[a]++;
        cnt[b]++;
      }
    }
    ll ans=0;
    for(auto[_,V]:mp){
      vec v;
      rep(i,V.size()){
        auto[x,y]=V[i];
        v.push_back(x);
        v.push_back(y);
      }    
      vec u=compress(v);
      ll sz=V.size()+1;
      Graph g(sz);
      rep(i,v.size()/2){
        ll x=v[2*i];
        ll y=v[2*i+1];
        g[x].push_back(y);
        g[y].push_back(x);
      }
      LCA lca(g,0);
      vector<P> U=mp2[_];
      for(auto[x,y]:U){
        x=lower_bound(all(u),x)-u.begin();
        y=lower_bound(all(u),y)-u.begin();
        ll z=lca.query(x,y);
        ans+=abs(lca.dist[x]-lca.dist[z])+abs(lca.dist[y]-lca.dist[z]);
      }
      vec now(sz);
      rep(i,u.size()){
        now[i]=cnt[u[i]];
      }
      auto f1=[&](P x,P y){
        auto[a,b]=x;
        auto[c,d]=y;
        a+=c;
        b+=d;
        return P(a,b);
      };
      auto f2=[&](P x,ll c,ll p){
        auto[a,b]=x;
        b+=now[c];
        a+=b;
        return P(a,b);
      };
      Rerooting<P,decltype(g),decltype(f1),decltype(f2)> dp(g,f1,f2,P(0,0));
      ll add=INF;
      for(auto [X,Y]:dp.dp){
        chmin(add,X);
      }
      ans+=add;
    }
    cout<<ans<<endl;
    return 0;
}
yukicoder

結果

ソースコード
