結果

問題 No.529 帰省ラッシュ
ユーザー m_tsubasam_tsubasa
提出日時 2020-06-04 11:06:46
言語 C++17
(gcc 13.2.0 + boost 1.83.0)
結果
AC  
実行時間 547 ms / 4,500 ms
コード長 6,475 bytes
コンパイル時間 4,106 ms
コンパイル使用メモリ 233,004 KB
実行使用メモリ 47,464 KB
最終ジャッジ日時 2023-08-18 20:40:33
合計ジャッジ時間 12,539 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge14
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
4,380 KB
testcase_01 AC 1 ms
4,380 KB
testcase_02 AC 2 ms
4,376 KB
testcase_03 AC 2 ms
4,376 KB
testcase_04 AC 8 ms
4,380 KB
testcase_05 AC 7 ms
4,376 KB
testcase_06 AC 8 ms
4,380 KB
testcase_07 AC 7 ms
4,380 KB
testcase_08 AC 457 ms
30,788 KB
testcase_09 AC 426 ms
30,548 KB
testcase_10 AC 460 ms
32,856 KB
testcase_11 AC 453 ms
33,100 KB
testcase_12 AC 412 ms
32,228 KB
testcase_13 AC 351 ms
47,464 KB
testcase_14 AC 449 ms
35,668 KB
testcase_15 AC 547 ms
34,328 KB
testcase_16 AC 532 ms
34,264 KB
testcase_17 AC 502 ms
44,932 KB
testcase_18 AC 521 ms
45,488 KB
testcase_19 AC 516 ms
42,268 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

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

// 0-indexed
template <class T>
struct SegmentTree {
  // a,b,c: T, e:T(unit)
  // abc = (ab)c = a(bc)
  // ae = ea = a
  typedef function<T(T, T)> F;
  int n;
  F f;
  T unit;
  vector<T> dat;
  SegmentTree(){};
  SegmentTree(int newn, F f, T t) : f(f), unit(t) { init(newn); }
  SegmentTree(const vector<T> &v, F f, T t) : f(f), unit(t) {
    int _n = v.size();
    init(v.size());
    for (int i = 0; i < _n; ++i) dat[n + i] = v[i];
    for (int i = n - 1; i; --i) dat[i] = f(dat[i << 1], dat[(i << 1) | 1]);
  }
  void init(int newn) {
    n = 1;
    while (n < newn) n <<= 1;
    dat.assign(n << 1, unit);
  }

  // "go up" process
  void update(int k, T newdata) {
    dat[k += n] = newdata;
    while (k >>= 1) {
      dat[k] = f(dat[(k << 1) | 0], dat[(k << 1) | 1]);
    }
  }
  // [a,b)
  T query(int a, int b) {
    T vl = unit, vr = unit;
    for (int l = a + n, r = b + n; l < r; l >>= 1, r >>= 1) {
      if (l & 1) vl = f(vl, dat[l++]);
      if (r & 1) vr = f(dat[--r], vr);
    }
    return f(vl, vr);
  }
};

struct HeavyLightDecomposition {
  int root;
  vector<vector<int>> g;
  vector<int> sz, par, dep, in, out, head;
  HeavyLightDecomposition(int n = 1, int _root = 0)
      : root(_root), g(n), sz(n), par(n), dep(n), in(n), out(n), head(n) {}
  HeavyLightDecomposition(const vector<vector<int>> &_g, const int _root = 0)
      : root(_root),
        g(_g),
        sz(_g.size()),
        par(_g.size()),
        dep(_g.size()),
        in(_g.size()),
        out(_g.size()),
        head(_g.size()) {
    build();
  }
  void add(int a, int b) {
    g[a].push_back(b);
    g[b].push_back(a);
  }
  void build() {
    dfs_sz(root, -1, 0);
    int t = 0;
    dfs_hld(root, -1, t);
  }
  void dfs_sz(int now, int bf, int d) {
    dep[now] = d;
    par[now] = bf;
    sz[now] = 1;
    if (g[now].size() && g[now][0] == bf) swap(g[now][0], g[now].back());
    for (auto &to : g[now]) {
      if (to == bf) continue;
      dfs_sz(to, now, d + 1);
      sz[now] += sz[to];
      if (sz[g[now][0]] < sz[to]) swap(g[now][0], to);
    }
  }
  void dfs_hld(int now, int bf, int &t) {
    in[now] = t++;
    for (auto &to : g[now]) {
      if (to == bf) continue;
      head[to] = (g[now][0] == to ? head[now] : to);
      dfs_hld(to, now, t);
    }
    out[now] = t;
  }
  int lca(int x, int y) {
    for (;; y = par[head[y]]) {
      if (in[x] > in[y]) swap(x, y);
      if (head[x] == head[y]) return x;
    }
  }
  int chil(int x, int y) { return dep[x] < dep[y] ? y : x; }
  //[l,r)
  template <typename F>
  void for_each(int x, int y, const F &f) {
    for (;; y = par[head[y]]) {
      if (in[x] > in[y]) swap(x, y);
      f(max(in[head[y]], in[x]), in[y] + 1);
      if (head[x] == head[y]) return;
    }
  }
  //[l,r)
  template <typename F>
  void for_eachedge(int x, int y, const F &f) {
    while (1) {
      if (in[x] > in[y]) swap(x, y);
      if (head[x] != head[y]) {
        f(in[head[y]], in[y] + 1);
        y = par[head[y]];
      } else {
        if (x != y) f(in[x] + 1, in[y] + 1);
        break;
      }
    }
  }
  template <typename T, typename F>
  void update(int node, T x, const F &f) {
    f(in[node], x);
    //    f(out[node], -x);
    // laze pattern
    // f(in[node], out[node], x);
  }
};

// TwoEdgeConnectedComponents + LowLink
struct TwoEdgeConnectedComponents {
  int n;
  vector<vector<int>> g;
  vector<int> ord, low, articulation, id;
  vector<bool> used;
  using P = pair<int, int>;
  vector<P> bridge;
  TwoEdgeConnectedComponents(int _n = 1) : n(_n), g(n) {}
  TwoEdgeConnectedComponents(vector<vector<int>> &_g) : n(_g.size()), g(_g) {
    lowlinkbuild();
  }

  bool add(int from, int to) {
    g[from].push_back(to);
    g[to].push_back(from);
    return 1;
  }

  void lowlinkbuild() {
    ord.assign(n, -1);
    low.assign(n, -1);
    int k = 0;
    for (int i = 0; i < n; ++i)
      if (ord[i] < 0) lowlinkdfs(i, -1, k);
  }
  void lowlinkdfs(int now, int par, int &k) {
    ord[now] = low[now] = k++;
    bool ch = 0;  // articulation
    int cnt = 0;
    for (auto &to : g[now])
      if (ord[to] < 0) {
        ++cnt;
        lowlinkdfs(to, now, k);
        low[now] = min(low[now], low[to]);
        ch |= ~par && low[to] >= ord[now];  // articulation
        if (ord[now] < low[to])
          bridge.emplace_back(min(now, to), max(now, to));  // bridge
      } else if (to != par)
        low[now] = min(low[now], ord[to]);
    ch |= par == -1 && cnt > 1;           // articulation
    if (ch) articulation.push_back(now);  // articulation
  }

  vector<vector<int>> build() {
    id.assign(n, -1);
    int k = 0;
    for (int i = 0; i < n; ++i)
      if (id[i] < 0) dfs(i, -1, k);
    vector<vector<int>> res(k);
    for (auto &e : bridge) {
      int x = id[e.first], y = id[e.second];
      res[x].push_back(y);
      res[y].push_back(x);
    }
    return res;
  }

  void dfs(int now, int par, int &k) {
    if (~par && ord[par] >= low[now])
      id[now] = id[par];
    else
      id[now] = k++;
    for (auto &to : g[now])
      if (id[to] < 0) dfs(to, now, k);
  }

  inline int operator[](const int &k) { return (id.at(k)); }
};

using P = pair<long long, long long>;
long long n, m, q;
TwoEdgeConnectedComponents tecc;
SegmentTree<P> seg;
HeavyLightDecomposition hld;
vector<vector<int>> g;
vector<priority_queue<long long>> lst;

int main() {
  cin >> n >> m >> q;
  g.resize(n);
  for (int i = 0; i < m; ++i) {
    int a, b;
    cin >> a >> b;
    g[--a].push_back(--b);
    g[b].push_back(a);
  }
  tecc = TwoEdgeConnectedComponents(g);
  hld = HeavyLightDecomposition(tecc.build());
  lst.resize(n);
  auto f = [](P l, P r) { return max(l, r); };
  seg = SegmentTree<P>(n, f, P(-1, -1));
  for (int i = 0; i < q; ++i) {
    int a, b, c;
    cin >> a >> b >> c;
    if (a == 1) {
      int x = tecc[--b];
      lst[x].push(c);
      auto updatef = [](int id, P num) { seg.update(id, num); };
      hld.update(x, P(lst[x].top(), x), updatef);
    } else {
      int x = tecc[--b], y = tecc[--c];
      P res(-1, -1);
      auto func = [&](int l, int r) { res = max(res, seg.query(l, r)); };
      hld.for_each(x, y, func);
      cout << res.first << endl;
      if (res.first > 0) {
        x = res.second;
        lst[x].pop();
        long long num = -1;
        if (lst[x].size()) num = lst[x].top();
        auto updatef = [](int id, P num) { seg.update(id, num); };
        hld.update(x, P(num, x), updatef);
      }
    }
  }
  return 0;
}
0