結果
| 問題 | No.3608 Golden Steiner Tree |
| コンテスト | |
| ユーザー |
 mitani
|
| 提出日時 | 2026-08-01 02:31:36 |
| 言語 | C++23(gcc16) (gcc 16.1.0 + boost 1.90.0) |
| 結果 |
AC
|
| 実行時間 | 915 ms / 3,000 ms |
| + 474µs | |
| コード長 | 5,997 bytes |
| 記録 | |
| コンパイル時間 | 4,801 ms |
| コンパイル使用メモリ | 369,740 KB |
| 実行使用メモリ | 54,656 KB |
| 最終ジャッジ日時 | 2026-08-01 02:31:48 |
| 合計ジャッジ時間 | 12,165 ms |
|
ジャッジサーバーID （参考情報） |
judge1_1 / judge3_0 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 20 |
ソースコード
#include <bits/stdc++.h>
#define rep(i,n) for(ll i=0;i<(ll)(n);i++)
#define Yes cout << "Yes" << "\n"
#define No cout << "No" << "\n"
#define rtr0 return(0)
#define all(x) x.begin(), x.end()
using namespace std;
//#include <atcoder/all>
//using namespace atcoder;
//using mint=static_modint<998244353>;
//using mint=static_modint<1000000007>;
////using mint=modint;
//#pragma GCC target("avx2")
//#pragma GCC optimize("O3")
//#pragma GCC optimize("unroll-loops")
using ll=long long;
using l3=__int128;
using ull=unsigned long long;
using ld=long double;
using P=pair<ll,ll>;
const ld PI=acos(-1);
template<typename T>bool chmin(T&a,T b){if(a>b){a=b;return true;}return false;}
template<typename T>bool chmax(T&a,T b){if(a<b){a=b;return true;}return false;}
void yn(bool f){cout<<(f?"Yes":"No")<<endl;}
const vector<int> dx={1,0,-1,0,1,-1,1,-1};
const vector<int> dy={0,1,0,-1,1,1,-1,-1};
const int inf=1001001001;
const ll INF=1001001001001001001;
//ll mod=998244353;
// LCA を求めるライブラリ
struct LCA {
vector<vector<int>> parent; // parent[d][v] := 2^d-th parent of v
vector<int> depth;
LCA() { }
LCA(const vector<vector<ll>> &g, int r = 0) { init(g, r); }
void init(const vector<vector<ll>> &g, int r = 0) {
int V = (int)g.size();
int h = 1;
while ((1<<h) < V) ++h;
parent.assign(h, vector<int>(V, -1));
depth.assign(V, -1);
dfs(g, r, -1, 0);
for (int i = 0; i+1 < (int)parent.size(); ++i)
for (int v = 0; v < V; ++v)
if (parent[i][v] != -1)
parent[i+1][v] = parent[i][parent[i][v]];
}
void dfs(const vector<vector<ll>> &g, int v, int p, int d) {
parent[0][v] = p;
depth[v] = d;
for (auto e : g[v]) if (e != p) dfs(g, e, v, d+1);
}
int get(int u, int v) {
if (depth[u] > depth[v]) swap(u, v);
for (int i = 0; i < (int)parent.size(); ++i)
if ( (depth[v] - depth[u]) & (1<<i) )
v = parent[i][v];
if (u == v) return u;
for (int i = (int)parent.size()-1; i >= 0; --i) {
if (parent[i][u] != parent[i][v]) {
u = parent[i][u];
v = parent[i][v];
}
}
return parent[0][u];
}
};
vector<ll> in,inr;
vector<ll> sumA,sumB;
ll cnt=0;
void dfs(ll pos,ll bef,vector<vector<P>>&g){
in[pos]=cnt;
inr[cnt]=pos;
cnt++;
for(auto[nxt,c]:g[pos]){
if(nxt==bef)continue;
if(c==0){
sumA[nxt]=sumA[pos]+1;
sumB[nxt]=sumB[pos];
}
if(c==1){
sumA[nxt]=sumA[pos];
sumB[nxt]=sumB[pos]+1;
}
dfs(nxt,pos,g);
}
}
//グラフは木
void solve(){
ll n,r,b;cin>>n>>r>>b;
in.resize(n);
inr.resize(n);
sumA.resize(n);
sumB.resize(n);
vector<vector<P>> g(n);
vector<vector<ll>> gg(n);
ld phi=(1+sqrt(5))/2;
for(int i=2;i<=n;i++){
if(floor(i*phi)<=n){
g[i-1].push_back({floor(i*phi)-1,0});
gg[i-1].push_back(floor(i*phi)-1);
}
}
for(int i=1;i<=n;i++){
if(floor(i*phi*phi)<=n){
g[i-1].push_back({floor(i*phi*phi)-1,1});
gg[i-1].push_back(floor(i*phi*phi)-1);
}
}
dfs(0,-1,g);
ll q;cin>>q;
set<ll> st;
vector<bool> f(n);
LCA Z(gg);
//for(auto x:in)cout<<x<<" ";
//cout<<endl;
//for(auto x:inr)cout<<x<<" ";
//cout<<endl;
//for(auto x:sumA)cout<<x<<" ";
//cout<<endl;
//for(auto x:sumB)cout<<x<<" ";
//cout<<endl;
ll ca=0,cb=0;
rep(_,q){
ll t,x;cin>>t>>x;
if(t==1){
x--;
ll id=in[x];
//黒から白
if(!f[x]){
f[x]=true;
if(st.size()==0){
st.insert(id);
ca=0,cb=0;
}
else{
auto it=st.lower_bound(id);
auto itr=it;
if(it==st.end())itr=st.begin();
auto itl=it;
if(it==st.begin())itl=st.end();
itl--;
ll L=inr[*itl];
ll R=inr[*itr];
//cout<<L<<" "<<x<<" "<<R<<endl;
ca+=sumA[L]+sumA[x]-2*sumA[Z.get(L,x)];
ca+=sumA[x]+sumA[R]-2*sumA[Z.get(x,R)];
ca-=sumA[L]+sumA[R]-2*sumA[Z.get(L,R)];
cb+=sumB[L]+sumB[x]-2*sumB[Z.get(L,x)];
cb+=sumB[x]+sumB[R]-2*sumB[Z.get(x,R)];
cb-=sumB[L]+sumB[R]-2*sumB[Z.get(L,R)];
st.insert(id);
}
}
//白から黒
else{
f[x]=false;
st.erase(id);
if(st.size()==0){
ca=0,cb=0;
}
else{
auto it=st.lower_bound(id);
auto itr=it;
if(it==st.end())itr=st.begin();
auto itl=it;
if(it==st.begin())itl=st.end();
itl--;
ll L=inr[*itl];
ll R=inr[*itr];
//cout<<L<<" "<<x<<" "<<R<<endl;
ca-=sumA[L]+sumA[x]-2*sumA[Z.get(L,x)];
ca-=sumA[x]+sumA[R]-2*sumA[Z.get(x,R)];
ca+=sumA[L]+sumA[R]-2*sumA[Z.get(L,R)];
cb-=sumB[L]+sumB[x]-2*sumB[Z.get(L,x)];
cb-=sumB[x]+sumB[R]-2*sumB[Z.get(x,R)];
cb+=sumB[L]+sumB[R]-2*sumB[Z.get(L,R)];
}
}
}
else if(t==2){
r=x;
}
else{
b=x;
}
//cout<<ca/2<<" "<<cb/2<<"\n";
cout<<(ca*r+cb*b)/2<<endl;
}
//cout<<endl;
}
int main(){
ll t=1;
//cin>>t;
rep(i,t)solve();
}
//銅3赤6橙4黄3青1水4