結果

問題 No.3134 二分探索木
ユーザー Facade
提出日時 2025-05-03 13:39:50
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,864 bytes
コンパイル時間 4,240 ms
コンパイル使用メモリ 280,184 KB
実行使用メモリ 15,616 KB
最終ジャッジ日時 2025-05-03 13:39:59
合計ジャッジ時間 7,954 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include<bits/stdc++.h>
#define int long long
using namespace std;
signed main(){
    int n;cin>>n;
    vector<int>a(n);
    for(int i=0;i<n;i++){
        int aa;cin>>aa;
        aa--;
        a[i]=aa;
    }
    const int inf=1e18;
    vector<pair<int,int>>to(n,{inf,inf});
    vector<int>b(n,0);
    for(int i=1;i<n;i++){
        int now=a[0];
        int deep=0;
        while(true){
            if(a[i]<now){
                if(to[now].first==inf){
                    to[now].first=a[i];
                    b[i]=deep+1;
                    break;
                }else{
                    now=to[now].first;
                    deep++;
                    continue;
                }
            }else{
                if(to[now].second==inf){
                    to[now].second=a[i];
                    b[i]=deep+1;
                    break;
                }else{
                    now=to[now].second;
                    deep++;
                    continue;
                }
            }
        }
    }
    for(int i=0;i<n;i++)cout<<b[i]<<" ";
    cout<<endl;
    vector<int>c(n,0);
    vector<bool>vis(n);
    vis[a[0]]=true;
    auto dfs=[&](auto dfs,int now)->int{
        int ret=1;
        if(to[now].first!=inf){
            if(!vis[to[now].first]){
                vis[to[now].first]=true;
                ret+=dfs(dfs,to[now].first);
            }
        }
        if(to[now].second!=inf){
            if(!vis[to[now].second]){
                vis[to[now].second]=true;
                ret+=dfs(dfs,to[now].second);
            }
        }
        c[now]=ret;
        return ret;
    };
    dfs(dfs,a[0]);
    for(int i=0;i<n;i++)cout<<c[a[i]]-1<<" ";
    cout<<endl;
    // for(int i=0;i<n;i++){
    //     cout<<"now -> "<<a[i]+1<<endl;;
    //     cout<<"first -> "<<to[a[i]].first+1<<" second -> "<<to[a[i]].second+1<<endl;
    // }
}
0