#569853 (C++17) No.529 帰省ラッシュ

提出ソース
結果

問題	No.529 帰省ラッシュ
コンテスト
ユーザー	kanra824
提出日時	2020-10-23 16:53:27
言語	C++17 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	687 ms / 4,500 ms
コード長	12,535 bytes
コンパイル時間	3,065 ms
コンパイル使用メモリ	225,728 KB
最終ジャッジ日時	2025-01-15 12:52:09
ジャッジサーバーID （参考情報）	judge2 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
sample	AC * 2
other	AC * 18
権限があれば一括ダウンロードができます
ソースコード

raw source code
#include <bits/stdc++.h>

using namespace std;

#define REP(i, n) for (int i=0; i<(n); ++i)
#define RREP(i, n) for (int i=(int)(n)-1; i>=0; --i)
#define FOR(i, a, n) for (int i=(a); i<(n); ++i)
#define RFOR(i, a, n) for (int i=(int)(n)-1; i>=(a); --i)

#define SZ(x) ((int)(x).size())
#define ALL(x) (x).begin(),(x).end()

#define DUMP(x) cerr<<#x<<" = "<<(x)<<endl
#define DEBUG(x) cerr<<#x<<" = "<<(x)<<" (L"<<__LINE__<<")"<<endl;

template<class T>
ostream &operator<<(ostream &os, const vector<T> &v) {
  os << "[";
  REP(i, SZ(v)) {
    if (i) os << ", ";
    os << v[i];
  }
  return os << "]";
}

template<class T, class U>
ostream &operator<<(ostream &os, const pair<T, U> &p) {
  return os << "(" << p.first << " " << p.second << ")";
}

template<class T>
bool chmax(T &a, const T &b) {
  if (a < b) {
    a = b;
    return true;
  }
  return false;
}

template<class T>
bool chmin(T &a, const T &b) {
  if (b < a) {
    a = b;
    return true;
  }
  return false;
}

using ll = long long;
using ull = unsigned long long;
using ld = long double;
using P = pair<int, int>;
using vi = vector<int>;
using vll = vector<ll>;
using vvi = vector<vi>;
using vvll = vector<vll>;

const ll MOD = 1e9 + 7;
const int INF = INT_MAX / 2;
const ll LINF = LLONG_MAX / 2;
const ld eps = 1e-9;

/**
 * @brief
 * 橋と関節点をO(n+m)で列挙
 * コンストラクタにグラフを投げ込むとbridgeとarticulationが更新される
 * @author Md
 * @date 2020/10/20
 */

struct Lowlink {
  vvi g;
  int n;
  vi ord, low;
  vector<P> bridge;
  vector<int> articulation;
  int t = 0;

  Lowlink(const vvi &G): g(G) {
    n = SZ(g);
    ord.resize(n, INF);
    low.resize(n, INF);

    REP(i, n) {
      if(ord[i] == INF) {
        dfs(i, -1);
      }
    }
  }

  void dfs(int now, int prev) {
    ord[now] = t;
    low[now] = ord[now];
    t++;
    int d = 0;
    bool ar = false;
    for(auto &nxt: g[now]) {
      if(nxt == prev) continue;
      if(ord[nxt] == INF) {
        d++;
        dfs(nxt, now);
        chmin(low[now], low[nxt]);
        ar |= prev != -1 && ord[now] <= low[nxt];
        if(ord[now] < low[nxt]) {
          if(now < nxt) bridge.emplace_back(now, nxt);
          else bridge.emplace_back(nxt, now);
        }
      } else {
        chmin(low[now], ord[nxt]);
      }
    }
    ar |= prev == -1 && d >= 2;
    if(ar) articulation.push_back(now);
  }
};

/**
 * @brief
 * 単純な無向グラフgを二重辺連結成分分解する
 *
 * 単純でないグラフについても
 *   自己ループ: 無視
 *   多重辺: メモっておいて、最後にunionfind
 * とすると二重辺連結成分がほぼ線形で求まる
 *
 * @author Md
 * @date 2020/10/21
 *
 */


struct TwoEdgeCC {
  vvi g;
  int n;
  Lowlink lowlink;
  vi comp;
  int id = 0;

  TwoEdgeCC(const vvi &g): g(g), lowlink(g) {
    n = SZ(g);
    comp.resize(n, -1);
    REP(i, n) {
      if(comp[i] == -1) {
        dfs(i, -1);
      }
    }
  }

  vvi build_graph() {
    vvi t(id);
    for(auto &e: lowlink.bridge) {
      int u = comp[e.first];
      int v = comp[e.second];
      t[u].push_back(v);
      t[v].push_back(u);
    }
    return t;
  }

private:
  void dfs(int now, int prev) {
    if(prev != -1 && lowlink.ord[prev] >= lowlink.low[now]) {
      comp[now] = comp[prev];
    } else {
      comp[now] = id;
      id++;
    }
    for(auto &nxt: g[now]) {
      if(comp[nxt] == -1) dfs(nxt, now);
    }
  }
};

struct HLDecomposition {

  /**
  * @brief コンストラクタ O(V)
  * @param[in] g: 無向木
  * @param[in] root: 根
  */
  HLDecomposition(const vector<vector<int>>& g, int root=0) :
      g(g), par(g.size()), size(g.size()), depth(g.size()),
      head(g.size()), vid(g.size()) {
    dfs(root, -1, 0);
    int k = 0;
    hld(root, root, k);
  }

  /**
  * @brief LCAを求める. O(logV)
  */
  int lca(int u, int v) const {
    for (;; v = par[head[v]]) {
      if (depth[head[u]] > depth[head[v]]) swap(u, v);
      if (head[u] == head[v]) {
        if (depth[u] > depth[v]) swap(u, v);
        return u;
      }
    }
  }

  /**
   * @brief 頂点u,v間の距離を取得する. O(logV)
   */
  int dist(int u, int v) {
    return depth[u] + depth[v] - 2 * depth[lca(u,v)];
  }

  /**
  * @brief 指定した2頂点間のパス上で更新クエリを実行する. O(logV)*O(q).
  * @param[in] u, v: 更新クエリを実行するパスの両端
  * @param[in] q: 実行する更新クエリ
  * @param[in] edge: 辺クエリか頂点クエリか
  * @details 使い方
  *     e.g. Range Update Query
  *     LazySegmentTree<int> segt(n);
  *       // 頂点v (辺クエリの場合は(par[v],v)) のデータがvid[v]に保存される
  *
  *     hld.update(u, v, [&](int s,int t){ segt.update(s, t, x); });
  *       // u, v 間の全ての頂点の値をx に変更する.
  *     hld.update(u, v, [&](int s,int t){ segt.update(s, t, x); }, true);
  *       // u, v 間の全ての辺の値をx に変更する.
  */
  template<class UpdateQuery>
  void update(int u, int v, const UpdateQuery& q, bool edge = false) const {
    for (;; v = par[head[v]]) {
      if (depth[head[u]] > depth[head[v]]) swap(u, v);
      if (head[u] == head[v]) {
        if (vid[u] > vid[v]) swap(u, v);
        q(vid[u] + edge, vid[v] + 1);
        break;
      } else {
        q(vid[head[v]], vid[v] + 1);
      }
    }
  }

  /**
  * @brief 指定した2頂点間のパス上で取得クエリを実行する. O(logV)*(O(q)+O(f))
  * @param[in] u, v: 取得クエリを実行するパスの両端
  * @param[in] q: 実行する取得クエリ
  * @param[in] f: 小分けにした区間から取得した値をマージする方法
  * @param[in] ident: fの単位元
  * @param[in] edge 辺クエリか頂点クエリか
  * @return 取得した値
  *
  * @details 使い方
  *     e.g. Range Minimum Query
  *     SegmentTree<int> segt;
  *       // 頂点v (辺クエリの場合は(par[v],v)) のデータがvid[v]に保存される
  *
  *     hld.query(u, v,
  *          [&](int s,int t){ return segt.query(s,t); },
  *          [&](int a,int b){ return min(a,b); }, INF);
  *       // u, v 間のパス上にある全ての頂点の値のminを取得する.
  */
  template<class Query, class MergeFunc, typename T>
  T query(int u, int v,
          const Query& q, const MergeFunc& f,
          const T& ident, bool edge = false) const {
    T ret = ident;
    for (;; v = par[head[v]]) {
      if (depth[head[u]] > depth[head[v]]) swap(u, v);
      if (head[u] == head[v]) {
        if (vid[u] > vid[v]) swap(u, v);
        return f(ret, q(vid[u] + edge, vid[v] + 1));
      } else {
        ret = f(ret, q(vid[head[v]], vid[v] + 1));
      }
    }
  }

private:
  const vector<vector<int>>& g;
  vector<int> par, size, depth, head, vid;
  // par[v]   : 頂点v の親頂点
  // size[v]  : 頂点v を根とした部分木の頂点数
  // depth[v] : 頂点v の深さ. 根の深さは0
  // head[v]  : HL分解した際に, 頂点v を含む区間の先頭に位置する頂点
  // vid[v]   : 頂点v に対応する内部index. HL分解した後の各区間上でvidは連続

  void dfs(int v, int p, int d) {
    par[v] = p; depth[v] = d; size[v] = 1;
    for (int u : g[v]) {
      if (u == p) continue;
      dfs(u, v, d+1);
      size[v] += size[u];
    }
  }
  void hld(int v, int h, int& k) {
    head[v] = h; vid[v] = k++;
    int ma = 0, id = -1;
    for (int u : g[v]) {
      if (u == par[v]) continue;
      if (chmax(ma, size[u])) id = u;
    }
    if (id == -1) return;
    hld(id, h, k);
    for (int u : g[v]) {
      if (u == id or u == par[v]) continue;
      hld(u, u, k);
    }
  }
};

template<typename M>
struct SegmentTree {

  /**
  * @brief コンストラクタ. O(n)
  * @param[in] n セグ木のサイズ.
  * @param[in] f モノイドの演算(query).
  * @param[in] g モノイドの演算(update).
  * @param[in] e モノイドの単位元.
  * @details 使い方
  *   e.g. Update and Range Minimum
  *   SegmentTree<int> segt(
  *            n,
  *            [](int a,int b){ return min(a+b); },
  *            [](int a, int b){ return b; },
  *            INF);
  *               // 全て単位元で初期化される.
  */
  SegmentTree(
      int n,
      const function<M(M,M)>& f,
      const function<M(M, M)>& g,
      const M& e) : n(n), f(f), g(g), e(e) {
    sz = 1;
    while (sz < n) sz <<= 1;
    data.assign(2 * sz, e);
  }

  /**
  * @brief 全体に初期値を入れる. O(n)
  * @param[in] v 要素モノイドのvector. 初期化する.
  * @details 使い方
  *   segt.build(vector<int>(n, 0));
  */
  void build(const vector<M>& v) {
    assert(v.size() <= n);
    for (int i = 0; i < v.size(); ++i) {
      data[i + sz] = v[i];
    }
    for (int i = sz-1; i > 0; --i) {
      data[i] = f(data[2 * i], data[2 * i + 1]);
    }
  }

  /**
   * @brief 指定した位置に更新クエリを実行する O(log n)
   * @param[in] idx 位置idxに作用させる
   * @param[in] val 値xをg(data[idx+sz], val)で更新する
   */
  void update(int idx, M val) {
    idx += sz;
    data[idx] = g(data[idx], val);
    while(idx >>= 1) {
      data[idx] = f(data[2*idx], data[2*idx+1]);
    }
  }

  /**
  * @brief 指定した区間に取得クエリを実行する. O(log n)
  * @param[in] l, r 区間[l, r) を取得する.
  * @return 取得した値.
  * @details 使い方
  *   e.g. Range Minimum
  *   int l, r; // 区間[l, r) のminを取得したい.
  *   cout << segt.query(l, r) << endl;
  */
  M query(int a, int b) const {
    return query(a, b, 1, 0, sz);
  }

  /**
  * @brief 指定したindexの要素を取得. O(1)
  * @param[in] i 取得したい要素のindex
  * @return 取得した値.
  */
  M operator[](int k) const {
    return data[k + sz];
  }

  /**
  * @brief vector みたいに出力.
  */
  friend ostream& operator<<(ostream& os, SegmentTree& s) {
    os << "[";
    for (int i = 0; i < s.n; ++i) {
      if (i) os << " ";
      os << s[i];
    }
    return os << "]";
  }

private:
  int n, sz;
  vector<M> data;
  const function<M(M,M)> f, g;
  const M e;

  M query(int a, int b, int k, int l, int r) const {
    if (r <= a || b <= l) {
      return e;
    } else if (a <= l && r <= b) {
      return data[k];
    } else {
      return f(query(a,b,2*k,  l,(l+r)/2),
               query(a,b,2*k+1,(l+r)/2,r));
    }
  }
};

int main() {
  cin.tie(0);
  ios::sync_with_stdio(false);
  cout << fixed << setprecision(10);

  int n, m, q; cin >> n >> m >> q;
  vvi g(n);
  REP(i, m) {
    int a, b; cin >> a >> b;
    a--; b--;
    g[a].push_back(b);
    g[b].push_back(a);
  }

  TwoEdgeCC tecc(g);
  auto t = tecc.build_graph();

  int sz = SZ(t);

  SegmentTree<P> st(
      sz+1,
      [](P a, P b){return max(a, b);},
      [](P a, P b){return b;},
      P(-1, sz)
      );

    HLDecomposition hld(t);

    vector<priority_queue<int>> pq(sz+1);

    REP(_, q) {
      int nowq; cin >> nowq;
      if(nowq == 1) {
        int u, w; cin >> u >> w;
        u = tecc.comp[u-1];
        int ma, idx;
        tie(ma, idx) = hld.query(u, u,
                           [&](int a, int b){return st.query(a, b);},
                           [&](P a, P b){return max(a, b);},
                           make_pair(-1, sz));
        if(ma < w) {
          pq[idx].push(ma);
          hld.update(u, u, [&](int a, int b){return st.update(a, {w, u});});
        } else {
          pq[u].push(w);
        };
      } else {
        int a, b; cin >> a >> b;
        a = tecc.comp[a-1];
        b = tecc.comp[b-1];
        int ma, idx;
        tie(ma, idx) = hld.query(
            a, b,
            [&](int a, int b){return st.query(a, b);},
            [&](P a, P b) {return max(a, b);},
            make_pair(-1, sz)
            );
        cout << ma << endl;


        if(idx == sz) continue;

        int nxt = -1;
        if(!pq[idx].empty()) {
          nxt = pq[idx].top();
          pq[idx].pop();
        }
        hld.update(idx, idx, [&](int a, int b){return st.update(a, {nxt, idx});});
      }
    }



  return 0;
}
yukicoder

結果

ソースコード
