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

• 問題: No.3608 Golden Steiner Tree
• ユーザー: abc864197532
• 提出日時: 2026-07-31 23:12:31
• 言語: C++23 (gcc 15.2.0 + boost 1.90.0)
• 結果: AC
• 実行時間: 269 ms / 3,000 ms
• コード長: 5,361 bytes
• コンパイル時間: 3,172 ms
• コンパイル使用メモリ: 360,200 KB
• 実行使用メモリ: 60,284 KB
• 最終ジャッジ日時: 2026-07-31 23:12:44
• 合計ジャッジ時間: 7,329 ms
• ジャッジサーバーID （参考情報）: judge1_0 / judge3_0

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

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int, int> pii;
#define pb push_back
#define all(a) a.begin(), a.end()
#define sz(a) ((int)a.size())
#ifdef Doludu
template <typename T>
ostream& operator << (ostream &o, vector <T> vec) {
    o << "{"; int f = 0;
    for (T i : vec) o << (f++ ? " " : "") << i;
    return o << "}";
}
void bug__(int c, auto ...a) {
    cerr << "\e[1;" << c << "m";
    (..., (cerr << a << " "));
    cerr << "\e[0m" << endl;
}
#define bug_(c, x...) bug__(c, __LINE__, "[" + string(#x) + "]", x)
#define bug(x...) bug_(32, x)
#define bugv(x...) bug_(36, vector(x))
#define safe bug_(33, "safe")
#else
#define bug(x...) void(0)
#define bugv(x...) void(0)
#define safe void(0)
#endif
const int mod = 998244353, N = 1000005;

struct Dsu {
    vector <int> rt, sz;
    int n, cc;
    Dsu () = default;
    Dsu (int _n) : n(_n), cc(_n) {
        rt.resize(n), iota(rt.begin(), rt.end(), 0);
        sz.assign(n, 1);
    }
    int Find(int v) {
        return rt[v] == v ? v : rt[v] = Find(rt[v]);
    }
    bool Union(int v, int u) {
        u = Find(u), v = Find(v);
        if (u == v) {
            return false;
        }
        if (sz[u] > sz[v]) {
            swap(u, v);
        }
        rt[u] = v;
        sz[v] += sz[u];
        cc--;
        return true;
    }
    bool same(int u, int v) {
        return Find(u) == Find(v);
    }
};

struct Tree {
    int n, lg;
    vector <vector <int>> adj, jump;
    vector <int> in, out, dep, s;
    void add_edge(int u, int v) {
        adj[u].pb(v), adj[v].pb(u);
    }
    void dfs(int v, int pa) {
        static int t = 0;
        jump[v][0] = pa, in[v] = t++, s[v] = 1;
        dep[v] = ~pa ? dep[pa] + 1 : 0;
        for (int i = 1; i < lg; ++i) {
            int k = jump[v][i - 1];
            jump[v][i] = ~k ? jump[k][i - 1] : -1;
        }
        for (int u : adj[v]) if (u != pa) {
            dfs(u, v);
            s[v] += s[u];
        }
        out[v] = t++;
    }
    bool anc(int u, int v) {
        return in[u] <= in[v] && out[u] >= out[v];
    }
    int lca(int u, int v) {
        if (anc(u, v)) return u;
        for (int i = lg - 1; ~i; --i) {
            int k = jump[u][i];
            if (~k && !anc(k, v)) u = k;
        }
        return jump[u][0];
    }
    int dis(int u, int v) {
        return dep[u] + dep[v] - 2 * dep[lca(u, v)];
    }
    void build(int rt = 0) {
        dfs(rt, -1);
    }
    Tree (int _n) : n(_n), lg(__lg(n) + 1), adj(n), jump(n, vector<int>(lg, -1)), in(n), out(n), dep(n), s(n) {}
};

int main() {
    ios::sync_with_stdio(false), cin.tie(0);
    int n, r, b;
    cin >> n >> r >> b;
    double phi = (1 + sqrt(5)) / 2;
    Dsu dsu(n + 1);
    vector <vector <pii>> adj(n + 1);
    Tree tree(n + 1);
    for (int i = 1; i <= n; ++i) {
        int x = floor(i * phi);
        int y = floor(i * phi * phi);
        if (x <= n && i != 1) {
            assert(dsu.Union(i, x));
            adj[i].emplace_back(x, 0);
            tree.add_edge(i, x);
        }
        if (y <= n) {
            assert(dsu.Union(i, y));
            adj[i].emplace_back(y, 1);
            tree.add_edge(i, y);
        }
    }
    tree.build(1);
    vector <int> in(n + 1);
    int t = 0;
    vector dep(2, vector(n + 1, 0));
    auto dfs = [&](auto self, int v) -> void {
        in[v] = t++;
        for (auto [u, w] : adj[v]) {
            dep[0][u] = dep[0][v];
            dep[1][u] = dep[1][v];
            dep[w][u]++;
            self(self, u);
        }
    };
    dfs(dfs, 1);
    set <pii> S;
    auto get = [&](int u, int v) -> pii {
        int l = tree.lca(u, v);
        return {dep[0][u] + dep[0][v] - 2 * dep[0][l], dep[1][u] + dep[1][v] - 2 * dep[1][l]};
    };
    int tot[2] = {0, 0};
    auto ins = [&](int v) {
        auto it = S.insert({in[v], v}).first;
        if (it != S.begin()) {
            auto [x, y] = get(prev(it)->second, v);
            tot[0] += x, tot[1] += y;
        }
        if (next(it) != S.end()) {
            auto [x, y] = get(next(it)->second, v);
            tot[0] += x, tot[1] += y;
        }
        if (it != S.begin() && next(it) != S.end()) {
            auto [x, y] = get(prev(it)->second, next(it)->second);
            tot[0] -= x, tot[1] -= y;
        }
    };
    auto del = [&](int v) {
        auto it = S.lower_bound({in[v], v});
        if (it != S.begin()) {
            auto [x, y] = get(prev(it)->second, v);
            tot[0] -= x, tot[1] -= y;
        }
        if (next(it) != S.end()) {
            auto [x, y] = get(next(it)->second, v);
            tot[0] -= x, tot[1] -= y;
        }
        if (it != S.begin() && next(it) != S.end()) {
            auto [x, y] = get(prev(it)->second, next(it)->second);
            tot[0] += x, tot[1] += y;
        }
        S.erase(it);
    };


    int q; cin >> q;
    vector <int> vis(n + 1);
    while (q--) {
        int op, x;
        cin >> op >> x;
        if (op == 1) {
            if (!vis[x]) vis[x] = 1, ins(x);
            else vis[x] = 0, del(x);
        } else if (op == 2) {
            r = x;
        } else {
            b = x;
        }
        if (tot[0] == 0 && tot[1] == 0) cout << "0\n";
        else {
            auto [x, y] = get(S.begin()->second, prev(S.end())->second);
            cout << (1ll * (tot[0] + x) * r + 1ll * (tot[1] + y) * b) / 2 << "\n";

        }
    }
}