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

• 問題: No.3608 Golden Steiner Tree
• ユーザー: hiro1729
• 提出日時: 2026-08-28 13:22:36
• 言語: C++23 (gcc 15.3.0 + boost 1.92.0)
• 結果: AC
• 実行時間: 93 ms / 3,000 ms
• コード長: 2,584 bytes
• コンパイル時間: 2,217 ms
• コンパイル使用メモリ: 340,448 KB
• 実行使用メモリ: 6,656 KB
• 最終ジャッジ日時: 2026-08-28 13:22:45
• 合計ジャッジ時間: 5,389 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

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

ソースコード

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

unsigned int isqrt(unsigned long long N) {
    if (N == 0) return 0;
    unsigned long long x = 2ULL << ((63 ^ countl_zero(N)) >> 1);
    do {
        x = (x + N / x) >> 1;
    } while (N < x * x);
    return x;
}

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

	int N, Q, cr = 0, cb = 0, lca = -1; ll R, B;
	cin >> N >> R >> B >> Q;
	vector<int> par(N + 1, -1), lc(N + 1, -1), rc(N + 1, -1);
	vector<int> D(N + 1);
	for (int i = 1; i <= N; i++) {
		int d = (i + isqrt((ll)i * i * 5)) >> 1;
		if (d <= N) {
			lc[i] = d; par[lc[i]] = i;
		}
		if (d + i <= N) {
			rc[i] = d + i; par[rc[i]] = i;
		}
	}
	lc[1] = -1; par[1] = -1;
	vector<bool> ch(N + 1), e(N + 1);
	int cnt = 0;
	while (Q--) {
		int t, x; cin >> t >> x;
		if (t == 1) {
			if (ch[x]) {
				ch[x] = false;
				int ce = 0;
				if (e[x]) ce++;
				if (lc[x] != -1 && e[lc[x]]) ce++;
				if (rc[x] != -1 && e[rc[x]]) ce++;
				if (ce == 1) {
					if ((lc[x] == -1 || !e[lc[x]]) && (rc[x] == -1 || !e[rc[x]])) {
						while (!ch[x] && e[x]) {
							if ((lc[x] != -1 && e[lc[x]]) || (rc[x] != -1 && e[rc[x]])) {
								break;
							}
							e[x] = false;
							if (x == lc[par[x]]) cr--;
							else cb--;
							x = par[x];
						}
					}
					if (!e[x]) {
						while (!ch[x]) {
							if ((lc[x] != -1 && e[lc[x]]) == (rc[x] != -1 && e[rc[x]])) {
								break;
							}
							if (lc[x] != -1 && e[lc[x]]) {
								x = lc[x]; cr--;
							} else {
								x = rc[x]; cb--;
							}
							e[x] = false;
						}
					}
				}
				cnt--;
				if (cnt == 0) lca = -1;
				else {
					while (e[x]) x = par[x];
					lca = x;
				}
			} else {
				ch[x] = true;
				if (!e[x] && (lc[x] == -1 || !e[lc[x]]) && (rc[x] == -1 || !e[rc[x]])) {
					if (lca == -1) {
						lca = x;
					} else {
						vector<int> S, T;
						S.push_back(lca);
						T.push_back(x);
						while (S.back() != 1) {
							S.push_back(par[S.back()]);
						}
						while (T.back() != 1) {
							T.push_back(par[T.back()]);
						}
						while (S.size() && T.size() && S.back() == T.back()) {
							S.pop_back(); T.pop_back();
						}
						for (int v: S) {
							if (e[v]) break;
							e[v] = true;
							if (v == lc[par[v]]) cr++;
							else cb++;
						}
						for (int v: T) {
							if (e[v]) break;
							e[v] = true;
							if (v == lc[par[v]]) cr++;
							else cb++;
						}
						lca = (S.size() ? par[S.back()] : par[T.back()]);
					}
				}
				cnt++;
			}
		} else {
			if (t == 2) R = x;
			else B = x;
		}
		cout << cr * R + cb * B << '\n';
	}
}