#1174363 (C++23) No.3608 Golden Steiner Tree

• 問題: No.3608 Golden Steiner Tree
• ユーザー: ぽえ
• 提出日時: 2026-07-30 22:44:33
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 186 ms / 3,000 ms
• コード長: 7,904 bytes
• コンパイル時間: 2,415 ms
• コンパイル使用メモリ: 353,248 KB
• 実行使用メモリ: 37,376 KB
• 最終ジャッジ日時: 2026-07-31 20:57:05
• 合計ジャッジ時間: 5,922 ms
• ジャッジサーバーID （参考情報）: judge1_1 / judge2_0

ファイルパターン	結果
sample	AC * 1
other	AC * 20

ソースコード

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

#line 2 "math/isqrt.hpp"

#include <cmath>
using namespace std;

// floor(sqrt(n)) を返す (ただし n が負の場合は 0 を返す)
long long isqrt(long long n) {
  if (n <= 0) return 0;
  long long x = sqrt(n);
  while ((x + 1) * (x + 1) <= n) x++;
  while (x * x > n) x--;
  return x;
}

#line 2 "tree/euler-tour.hpp"



#line 2 "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([[maybe_unused]] 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
 */
#line 6 "tree/euler-tour.hpp"

template <typename G>
struct EulerTour {
 private:
  struct RMQ {
    int n, s;
    using P = pair<int, int>;
    vector<P> seg;
    P UNIT = P(1 << 30, -1);

    RMQ(int N) : n(N), s(1) {
      while (s < N) s <<= 1;
      seg.assign(2 * s, UNIT);
    }

    void set(int k, P x) { seg[k + s] = x; }

    P operator[](int k) const { return seg[k + s]; }

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

    P query(int a, int b) const {
      P R = UNIT;
      for (a += s, b += s; a < b; a >>= 1, b >>= 1) {
        if (a & 1) R = min(R, seg[a++]);
        if (b & 1) R = min(R, seg[--b]);
      }
      return R;
    }

    int size() const { return n; }
  };

  vector<int> down, up;
  int id;
  RMQ rmq;

  void init(G &g, int root) {
    dfs(g, root, -1, 0);
    if (id < rmq.size()) rmq.set(id++, {-1, -1});
    for (int i = 0; i < (int)g.size(); i++) {
      if (down[i] == -1) {
        rmq.set(id++, {-1, -1});
        dfs(g, i, -1, 0);
        if (id < rmq.size()) rmq.set(id++, {-1, -1});
      }
    }
    rmq.build();
  }

  void dfs(G &g, int c, int p, int dp) {
    down[c] = id;
    rmq.set(id++, {dp, c});
    for (auto &d : g[c]) {
      if (d == p) continue;
      dfs(g, d, c, dp + 1);
    }
    up[c] = id;
    if (p != -1) rmq.set(id++, {dp - 1, p});
  }

 public:
  // remind : because of additional node,
  // DS on tour should reserve 2 * n nodes.
  EulerTour(G &g, int root = 0)
      : down(g.size(), -1), up(g.size(), -1), id(0), rmq(2 * g.size()) {
    init(g, root);
  }

  pair<int, int> idx(int i) const { return {down[i], up[i]}; }

  int lca(int a, int b) const {
    if (down[a] > down[b]) swap(a, b);
    return rmq.query(down[a], down[b] + 1).second;
  }

  template <typename F>
  void node_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l], down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void edge_query(int a, int b, const F &f) {
    int l = lca(a, b);
    f(down[l] + 1, down[a] + 1);
    f(down[l] + 1, down[b] + 1);
  }

  template <typename F>
  void subtree_query(int a, const F &f) {
    f(down[a], up[a]);
  }

  int size() const { return int(rmq.size()); }
};

/**
 * @brief オイラーツアー
 * @docs docs/tree/euler-tour.md
 */


using ll = long long;
using pll = pair<ll, ll>;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    ll r, b;
    cin >> n >> r >> b;

    UnweightedGraph g(n);
    vector<ll> dr(n), db(n);

    for (ll i = 1; i <= n; i++) {
        ll a = (i + isqrt(5 * i * i)) / 2;
        ll c = i + a;

        int p = int(i - 1);

        if (a != i && a <= n) {
            int v = int(a - 1);

            g[p].push_back(v);
            g[v].push_back(p);

            dr[v] = dr[p] + 1;
            db[v] = db[p];
        }

        if (c <= n) {
            int v = int(c - 1);

            g[p].push_back(v);
            g[v].push_back(p);

            dr[v] = dr[p];
            db[v] = db[p] + 1;
        }
    }

    EulerTour<UnweightedGraph> et(g, 0);

    vector<int> down(n);
    for (int v = 0; v < n; v++) {
        down[v] = et.idx(v).first;
    }

    auto d = [&](int u, int v) -> pll {
        int w = et.lca(u, v);

        return {
            dr[u] + dr[v] - 2 * dr[w],
            db[u] + db[v] - 2 * db[w],
        };
    };

    set<pair<int, int>> white;

    ll cr = 0, cb = 0;

    int q;
    cin >> q;

    while (q--) {
        int type;
        ll x;
        cin >> type >> x;

        if (type == 1) {
            int v = int(x - 1);
            pair<int, int> key{down[v], v};

            auto it = white.lower_bound(key);
            bool is_white = it != white.end() && *it == key;

            if (!is_white) {
                if (!white.empty()) {
                    auto next_it = (it == white.end() ? white.begin() : it);

                    auto prev_it = (it == white.begin() ? prev(white.end()) : prev(it));

                    int s = prev_it->second;
                    int t = next_it->second;

                    auto [svr, svb] = d(s, v);
                    auto [vtr, vtb] = d(v, t);
                    auto [str, stb] = d(s, t);

                    cr += (svr + vtr - str) / 2;
                    cb += (svb + vtb - stb) / 2;
                }

                white.insert(key);
            } else {
                if (white.size() >= 2) {
                    auto next_it = next(it);
                    if (next_it == white.end()) {
                        next_it = white.begin();
                    }

                    auto prev_it = (it == white.begin() ? prev(white.end()) : prev(it));

                    int s = prev_it->second;
                    int t = next_it->second;

                    auto [svr, svb] = d(s, v);
                    auto [vtr, vtb] = d(v, t);
                    auto [str, stb] = d(s, t);

                    cr -= (svr + vtr - str) / 2;
                    cb -= (svb + vtb - stb) / 2;
                }

                white.erase(it);
            }
        } else if (type == 2) {
            r = x;
        } else {
            b = x;
        }

        cout << r * cr + b * cb << '\n';
    }
}