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

提出ソース

結果

問題	No.529 帰省ラッシュ
ユーザー	penguinshunya
提出日時	2019-07-10 14:05:30
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	AC
実行時間	770 ms / 4,500 ms
コード長	5,688 bytes
コンパイル時間	3,439 ms
コンパイル使用メモリ	239,576 KB
実行使用メモリ	51,972 KB
最終ジャッジ日時	2024-04-23 04:59:02
合計ジャッジ時間	13,064 ms
ジャッジサーバーID （参考情報）	judge1 / judge4

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	2 ms 6,812 KB
testcase_01	AC	2 ms 6,816 KB
testcase_02	AC	2 ms 6,940 KB
testcase_03	AC	2 ms 6,944 KB
testcase_04	AC	9 ms 6,940 KB
testcase_05	AC	10 ms 6,944 KB
testcase_06	AC	10 ms 6,944 KB
testcase_07	AC	10 ms 6,940 KB
testcase_08	AC	633 ms 23,392 KB
testcase_09	AC	625 ms 24,308 KB
testcase_10	AC	660 ms 31,100 KB
testcase_11	AC	682 ms 31,528 KB
testcase_12	AC	521 ms 25,188 KB
testcase_13	AC	545 ms 51,972 KB
testcase_14	AC	613 ms 26,700 KB
testcase_15	AC	756 ms 35,116 KB
testcase_16	AC	770 ms 35,172 KB
testcase_17	AC	707 ms 44,548 KB
testcase_18	AC	696 ms 44,896 KB
testcase_19	AC	705 ms 42,248 KB

権限があれば一括ダウンロードができます

ソースコード

raw source code

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

struct UnWeightedGraph {
  struct Edge {
    int to;
    Edge(int to) : to(to) {}
  };
  vector<vector<Edge>> edges;
  int n;
  UnWeightedGraph(int n) : n(n) {
    edges.assign(n, vector<Edge>());
  }
  void add_edge(int v, int u) {
    edges[v].emplace_back(u);
  }
  vector<Edge> &operator[](int x) {
    return edges[x];
  }
};

template <typename Graph>
struct LowLink {
  using A = vector<int>;
  using B = vector<pair<int, int>>;
  Graph &g;
  int n;
  vector<bool> seen;
  vector<int> ord, low;
  A articulation;
  B bridge;
  LowLink(Graph &g) : g(g), n(g.n) {}
  void dfs(int v, int p, int &k) {
    seen[v] = true;
    ord[v] = k++;
    low[v] = ord[v];
    bool is = false;
    int cnt = 0;
    for (auto e : g[v]) {
      int u = e.to;
      if (seen[u])  {
        if (u != p) low[v] = min(low[v], ord[u]);
        continue;
      }
      cnt++;
      dfs(u, v, k);
      low[v] = min(low[v], low[u]);
      if (p != -1 && ord[v] <= low[u]) is = true;
      if (ord[v] < low[u]) bridge.emplace_back(minmax(v, u));
    }
    if (p == -1 && cnt > 1) is = true;
    if (is) articulation.push_back(v);
  }
  pair<A, B> build() {
    seen.assign(n, false);
    ord.assign(n, 0);
    low.assign(n, 0);
    articulation.clear();
    bridge.clear();
    int k = 0;
    dfs(0, -1, k);
    return pair<A, B>(articulation, bridge);
  }
  pair<A, B> operator()() {
    return build();
  }
};

template <typename Graph>
struct TwoEdgeConnectedComponent {
  using B = vector<pair<int, int>>;
  Graph &g;
  int n;
  vector<bool> seen;
  vector<int> group;
  set<pair<int, int>> b;
  TwoEdgeConnectedComponent(Graph &g) : g(g), n(g.n), group(n) {}
  void dfs(int v, int p, int k) {
    seen[v] = true;
    group[v] = k;
    for (auto e : g[v]) {
      int u = e.to;
      if (u == p) continue;
      if (seen[u]) continue;
      if (b.find(minmax(v, u)) != b.end()) continue;
      dfs(u, v, k);
    }
  }
  vector<int> decompose(B bridge) {
    seen.assign(n, false);
    b.clear();
    b.insert(bridge.begin(), bridge.end());
    int k = 0;
    for (int i = 0; i < n; i++) {
      if (seen[i]) continue;
      dfs(i, -1, k++);
    }
    return group;
  }
  vector<int> operator()(B bridge) {
    return decompose(bridge);
  }
};

template <typename T>
struct SegmentTree {
  using F = function<T(T, T)>;
  vector<T> v;
  F f;
  T e;
  int n;
  SegmentTree(int size, F f, T e) : f(f), e(e) {
    n = 1;
    while (n < size) n <<= 1;
    v.resize(n * 2, e);
  }
  void set(int k, T x) {
    v[k + n] = x;
  }
  void build() {
    for (int i = n - 1; i > 0; i--) {
      v[i] = f(v[i * 2 + 0], v[i * 2 + 1]);
    }
  }
  void update(int k, T x) {
    v[k += n] = x;
    while (k >>= 1) v[k] = f(v[k * 2 + 0], v[k * 2 + 1]);
  }
  T query(int a, int b) {
    T l = e, r = e;
    for (a += n, b += n; a < b; a >>= 1, b >>= 1) {
      if (a & 1) l = f(l, v[a++]);
      if (b & 1) r = f(v[--b], r);
    }
    return f(l, r);
  }
};

template <typename Graph>
struct HeavyLightDecomposition {
  Graph &g;
  int n;
  vector<int> par;
  vector<int> next;
  vector<int> vid;
  vector<int> head;
  HeavyLightDecomposition(Graph &g)
    : g(g), n(g.n), par(n), next(n, -1), vid(n), head(n) {}
  int dfs(int v = 0, int p = -1) {
    par[v] = p;
    int mx = 0, ret = 1;
    for (auto e : g[v]) {
      if (e.to == p) continue;
      int r = dfs(e.to, v);
      ret += r;
      if (mx < r) mx = r, next[v] = e.to;
    }
    return ret;
  }
  void bfs(int r = 0) {
    int k = 0;
    queue<int> q;
    q.emplace(r);
    while (!q.empty()) {
      auto h = q.front(); q.pop();
      for (int v = h; v != -1; v = next[v]) {
        vid[v] = k++;
        head[v] = h;
        for (auto e : g[v]) {
          if (e.to == par[v] || e.to == next[v]) continue;
          q.emplace(e.to);
        }
      }
    }
  }
  vector<int> build() {
    dfs();
    bfs();
    return vid;
  }
  void for_each(int v, int u, const function<void(int, int)> &f) {
    while (true) {
      if (vid[u] > vid[v]) swap(v, u);
      f(max(vid[head[v]], vid[u]), vid[v]);
      if (head[u] != head[v]) v = par[head[v]];
      else break;
    }
  }
};

int main() {
  int N, M, Q; cin >> N >> M >> Q;
  auto graph = UnWeightedGraph(N);
  for (int i = 0; i < M; i++) {
    int v, u; cin >> v >> u;
    v--, u--;
    graph.add_edge(v, u);
    graph.add_edge(u, v);
  }
  auto low = LowLink<UnWeightedGraph>(graph);
  auto two = TwoEdgeConnectedComponent<UnWeightedGraph>(graph);
  auto lll = low.build();
  auto dict = two.decompose(lll.second);
  
  int V = *max_element(dict.begin(), dict.end()) + 1;
  auto hraph = UnWeightedGraph(V);
  for (int i = 0; i < N; i++) {
    for (auto e : graph[i]) {
      if (dict[i] == dict[e.to]) continue;
      hraph.add_edge(dict[i], dict[e.to]);
    }
  }
  auto hld = HeavyLightDecomposition<UnWeightedGraph>(hraph);
  auto vid = hld.build();

  auto seg = SegmentTree<int>(V, [](int a, int b) {
    return max(a, b);
  }, -1);

  vector<priority_queue<int>> q(V);
  unordered_map<int, int> ma;
  for (int i = 0; i < Q; i++) {
    int n; cin >> n;
    if (n == 1) {
      int u, w; cin >> u >> w;
      u--;
      u = vid[dict[u]];
      if (q[u].empty() || q[u].top() < w) {
        seg.update(u, w);
      }
      q[u].emplace(w);
      ma[w] = u;
    } else {
      int s, t; cin >> s >> t;
      s--, t--;
      int ans = -1;
      s = dict[s], t = dict[t];
      hld.for_each(s, t, [&](int l, int r) {
        ans = max(ans, seg.query(l, r + 1));
      });
      cout << ans << '\n';
      if (ans != -1) {
        int u = ma[ans];
        q[u].pop();
        seg.update(u, q[u].size() > 0 ? q[u].top() : -1);
      }
    }
  }
  return 0;
}

yukicoder

結果

テストケース

ソースコード