#1174604 (C++17) No.3608 Golden Steiner Tree

• 問題: No.3608 Golden Steiner Tree
• ユーザー: Rubikun
• 提出日時: 2026-07-31 23:18:06
• 言語: C++17 (gcc 15.2.0 + boost 1.90.0)
• 結果: RE
• 実行時間: -
• コード長: 3,107 bytes
• コンパイル時間: 1,418 ms
• コンパイル使用メモリ: 214,616 KB
• 実行使用メモリ: 8,960 KB
• 最終ジャッジ日時: 2026-07-31 23:18:12
• 合計ジャッジ時間: 4,360 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge3_0

ファイルパターン	結果
sample	AC * 1
other	AC * 13 RE * 7

ソースコード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return true; } return false; }
template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return true; } return false; }
#define vi vector<int>
#define vl vector<ll>
#define vii vector<pair<int,int>>
#define vll vector<pair<ll,ll>>
#define vvi vector<vector<int>>
#define vvl vector<vector<ll>>
#define vvii vector<vector<pair<int,int>>>
#define vvll vector<vector<pair<ll,ll>>>
#define vst vector<string>
#define pii pair<int,int>
#define pll pair<ll,ll>
#define pb push_back
#define all(x) (x).begin(),(x).end()
#define mkunique(x) sort(all(x));(x).erase(unique(all(x)),(x).end())
#define fi first
#define se second
#define mp make_pair
#define si(x) int(x.size())
const int mod=998244353,MAX=500005,INF=15<<26;

int dp[MAX][3];
int par[MAX],G[MAX][2];

int main(){
    
    std::ifstream in("text.txt");
    std::cin.rdbuf(in.rdbuf());
    cin.tie(0);
    ios::sync_with_stdio(false);
    
    
    double s=(1.0+sqrt(5))/2,t=s*s;
    ll N,R,B;cin>>N>>R>>B;
    ll Q;cin>>Q;
    vl state(N+1);
    ll sz=0;
    for(int i=1;i<=N;i++){
        int x=floor(i*s),y=floor(i*t);
        if(x!=1){
            G[i][0]=x;
            par[x]=i;
        }
        {
            G[i][1]=y;
            par[y]=~i;
        }
    }
    while(Q--){
        int t;cin>>t;
        ll x;cin>>x;
        if(t==1){
            if(state[x]){
                state[x]=false;
                sz--;
            }else{
                state[x]=true;
                sz++;
            }
            
            int now=x;
            while(now>=1){
                //cout<<now<<" ";
                int l=G[now][0],r=G[now][1];
                dp[now][0]=state[now]+dp[l][0]+dp[r][0];
                dp[now][1]=dp[now][2]=0;
                if(dp[l][0]){
                    dp[now][1]++;
                    dp[now][1]+=dp[l][1];
                    dp[now][2]+=dp[l][2];
                }
                if(dp[r][0]){
                    dp[now][2]++;
                    dp[now][1]+=dp[r][1];
                    dp[now][2]+=dp[r][2];
                }
                if(par[now]>0) now=par[now];
                else now=~par[now];
            }
        }
        if(t==2){
            R=x;
        }
        if(t==3){
            B=x;
        }
        if(sz<=1) cout<<0<<"\n";
        else{
            int now=1;
            while(1){
                int l=G[now][0],r=G[now][1];
                if(dp[l][0]>0&&dp[l][0]!=sz){
                    cout<<dp[now][1]*R+dp[now][2]*B<<"\n";
                    break;
                }
                if(dp[r][0]>0&&dp[r][0]!=sz){
                    cout<<dp[now][1]*R+dp[now][2]*B<<"\n";
                    break;
                }
                //cout<<l<<" "<<r<<" "<<dp[l][0]<<" "<<dp[r][0]<<" "<<sz<<" "<<dp[now][0]<<endl;
                if(dp[l][0]==sz){
                    now=l;
                }else{
                    assert(dp[r][0]==sz);
                    now=r;
                }
            }
        }
    }
}