結果

問題 No.529 帰省ラッシュ
ユーザー ei1333333ei1333333
提出日時 2018-09-17 00:01:55
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 303 ms / 4,500 ms
コード長 6,581 bytes
コンパイル時間 2,798 ms
コンパイル使用メモリ 233,616 KB
実行使用メモリ 53,956 KB
最終ジャッジ日時 2024-07-18 07:33:55
合計ジャッジ時間 7,543 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 1 ms
5,248 KB
testcase_01 AC 3 ms
5,376 KB
testcase_02 AC 3 ms
5,376 KB
testcase_03 AC 3 ms
6,944 KB
testcase_04 AC 5 ms
6,940 KB
testcase_05 AC 5 ms
6,944 KB
testcase_06 AC 5 ms
6,944 KB
testcase_07 AC 6 ms
6,940 KB
testcase_08 AC 255 ms
28,052 KB
testcase_09 AC 235 ms
26,828 KB
testcase_10 AC 242 ms
28,392 KB
testcase_11 AC 242 ms
28,468 KB
testcase_12 AC 203 ms
30,020 KB
testcase_13 AC 245 ms
53,956 KB
testcase_14 AC 240 ms
36,000 KB
testcase_15 AC 303 ms
29,760 KB
testcase_16 AC 301 ms
29,728 KB
testcase_17 AC 275 ms
45,300 KB
testcase_18 AC 268 ms
46,008 KB
testcase_19 AC 274 ms
41,280 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>

using namespace std;

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 > >;
template< typename T >
using Matrix = vector< vector< T > >;

template< typename G >
struct HeavyLightDecomposition {
  G &g;
  vector< int > sz, in, out, head, rev, par;

  HeavyLightDecomposition(G &g) :
      g(g), sz(g.size()), in(g.size()), out(g.size()), head(g.size()), rev(g.size()), par(g.size()) {}

  void dfs_sz(int idx, int p) {
    par[idx] = p;
    sz[idx] = 1;
    if(g[idx].size() && g[idx][0] == p) swap(g[idx][0], g[idx].back());
    for(auto &to : g[idx]) {
      if(to == p) continue;
      dfs_sz(to, idx);
      sz[idx] += sz[to];
      if(sz[g[idx][0]] < sz[to]) swap(g[idx][0], to);
    }
  }

  void dfs_hld(int idx, int par, int &times) {
    in[idx] = times++;
    rev[in[idx]] = idx;
    for(auto &to : g[idx]) {
      if(to == par) continue;
      head[to] = (g[idx][0] == to ? head[idx] : to);
      dfs_hld(to, idx, times);
    }
    out[idx] = times;
  }

  void build() {
    dfs_sz(0, -1);
    int t = 0;
    dfs_hld(0, -1, t);
  }

  int lca(int u, int v) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) return u;
    }
  }

  template< typename T, typename Q, typename F >
  T query(int u, int v, const T &ti, const Q &q, const F &f, bool edge = false) {
    T l = ti, r = ti;
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v), swap(l, r);
      if(head[u] == head[v]) break;
      l = f(q(in[head[v]], in[v] + 1), l);
    }
    return f(f(q(in[u] + edge, in[v] + 1), l), r);
  }

  template< typename Q >
  void add(int u, int v, const Q &q, bool edge = false) {
    for(;; v = par[head[v]]) {
      if(in[u] > in[v]) swap(u, v);
      if(head[u] == head[v]) break;
      q(in[head[v]], in[v] + 1);
    }
    q(in[u] + edge, in[v] + 1);
  }
};

struct UnionFind {
  vector< int > data;

  UnionFind(int sz) {
    data.assign(sz, -1);
  }

  bool unite(int x, int y) {
    x = find(x), y = find(y);
    if(x == y) return (false);
    if(data[x] > data[y]) swap(x, y);
    data[x] += data[y];
    data[y] = x;
    return (true);
  }

  int find(int k) {
    if(data[k] < 0) return (k);
    return (data[k] = find(data[k]));
  }

  int size(int k) {
    return (-data[find(k)]);
  }
};

template< typename G >
struct LowLink {
  const G &g;
  UnionFind uf;
  vector< int > used, ord, low, parent;

  LowLink(const G &g) : g(g), uf(g.size()), used(g.size()), ord(g.size()), low(g.size()), parent(g.size(), -1) {}

  void dfs(int idx, int &k, int par = -1) {
    used[idx] = true;
    ord[idx] = k++;
    low[idx] = ord[idx];

    for(auto &to : g[idx]) {
      if(!used[to]) {
        dfs(to, k, idx);
        low[idx] = min(low[idx], low[to]);
        parent[to] = idx;
        if(ord[idx] >= low[to]) uf.unite(idx, to);
      } else if(to != par) {
        low[idx] = min(low[idx], ord[to]);
      }
    }
  }

  void dfs() {
    int k = 0;
    dfs(0, k);
  }
};

template< typename G >
struct BiConnectedComponents : LowLink< G > {
  using LL = LowLink< G >;

  vector< int > comp;

  BiConnectedComponents(const G &g) : LL(g), comp(g.size()) {}

  int operator[](int k) {
    return (comp[k]);
  }

  vector< pair< int, int > > build(UnWeightedGraph &t) {
    LL::dfs();
    int ptr = 0;
    vector< int > cc(LL::g.size());
    for(int i = 0; i < LL::g.size(); i++) {
      if(i == LL::uf.find(i)) cc[i] = ptr++;
    }

    t.resize(ptr);
    for(int i = 0; i < LL::g.size(); i++) {
      comp[i] = cc[LL::uf.find(i)];
    }

    vector< pair< int, int > > edges;
    for(int i = 0; i < LL::g.size(); i++) {
      for(auto &to : LL::g[i]) edges.emplace_back(minmax(i, to));
    }
    sort(begin(edges), end(edges));
    edges.erase(unique(begin(edges), end(edges)), end(edges));
    vector< pair< int, int > > vs;
    for(auto &e : edges) {
      int x = comp[e.first], y = comp[e.second];
      if(x == y) continue;
      vs.emplace_back(e.first, e.second);
      t[x].push_back(y);
      t[y].push_back(x);
    }
    sort(begin(vs), end(vs));
    return (vs);
  }
};


template< typename Monoid >
struct SegmentTree {
  using F = function< Monoid(Monoid, Monoid) >;

  int sz;
  vector< Monoid > seg;

  const F f;
  const Monoid M1;

  SegmentTree(int n, const F f, const Monoid &M1) : f(f), M1(M1) {
    sz = 1;
    while(sz < n) sz <<= 1;
    seg.assign(2 * sz, M1);
  }

  void set(int k, const Monoid &x) {
    seg[k + sz] = x;
  }

  void build() {
    for(int k = sz - 1; k > 0; k--) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  void update(int k, const Monoid &x) {
    k += sz;
    seg[k] = x;
    while(k >>= 1) {
      seg[k] = f(seg[2 * k + 0], seg[2 * k + 1]);
    }
  }

  Monoid query(int a, int b) {
    Monoid L = M1, R = M1;
    for(a += sz, b += sz; a < b; a >>= 1, b >>= 1) {
      if(a & 1) L = f(L, seg[a++]);
      if(b & 1) R = f(seg[--b], R);
    }
    return f(L, R);
  }

  Monoid operator[](const int &k) const {
    return seg[k + sz];
  }
};


int main() {
  int N, M, Q;

  scanf("%d %d %d", &N, &M, &Q);
  UnWeightedGraph g(N);
  BiConnectedComponents< UnWeightedGraph > bc(g);
  for(int i = 0; i < M; i++) {
    int A, B;
    scanf("%d %d", &A, &B);
    --A, --B;
    g[A].emplace_back(B);
    g[B].emplace_back(A);
  }
  vector< vector< int > > graph;
  bc.build(graph);
  HeavyLightDecomposition< UnWeightedGraph > hld(graph);
  hld.build();
  auto f = [](int a, int b) { return max(a, b); };
  SegmentTree< int > seg(graph.size(), f, -1);

  vector< priority_queue< int > > que(graph.size());
  unordered_map< int, int > pos;

  for(int i = 0; i < Q; i++) {
    int T, A, B;
    scanf("%d %d %d", &T, &A, &B);
    if(T == 1) {
      A = bc[--A];
      pos[B] = A;
      que[A].push(B);
      if(que[A].top() == B) seg.update(hld.in[A], que[A].top());
    } else {
      int value = hld.query(bc[--A], bc[--B], -1, [&](int a, int b) { return seg.query(a, b); }, [](int a, int b) { return max(a, b); });
      printf("%d\n", value);
      if(value >= 1) {
        int idx = pos[value];
        que[idx].pop();
        seg.update(hld.in[idx], que[idx].empty() ? -1 : que[idx].top());
      }
    }
  }
}
0