結果

問題 No.3608 Golden Steiner Tree
コンテスト
ユーザー Rubikun
提出日時 2026-07-31 23:18:50
言語 C++17
(gcc 15.2.0 + boost 1.90.0)
コンパイル:
g++-15 -O2 -lm -std=c++17 -Wuninitialized -DONLINE_JUDGE -o a.out _filename_
実行:
./a.out
結果
AC  
実行時間 75 ms / 3,000 ms
+ 673µs
コード長 3,107 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 1,223 ms
コンパイル使用メモリ 214,884 KB
実行使用メモリ 10,880 KB
最終ジャッジ日時 2026-07-31 23:19:02
合計ジャッジ時間 4,069 ms
ジャッジサーバーID
（参考情報） 		judge1_0 / judge3_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 1
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#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=550005,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;
                }
            }
        }
    }
}
0