結果

問題 No.3134 二分探索木
コンテスト
ユーザー しょうゆ団子
提出日時 2025-05-05 01:15:55
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,223 bytes
コンパイル時間 3,507 ms
コンパイル使用メモリ 278,680 KB
実行使用メモリ 16,072 KB
最終ジャッジ日時 2025-05-05 01:16:03
合計ジャッジ時間 7,960 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>

using namespace std;

int main() {
    int N;
    cin >> N;
    vector<int> A(N), L(N, -1), R(N, -1), P(N, -1);
    cin >> A[0];
    A[0]--;
    auto insert = [&] (auto insert, int p, int i) {
        if (p < i) {
            if (R[p] == -1) {
                R[p] = i;
                P[i] = p;
                return;
            }
            insert(insert, R[p], i);
        } else {
            if (L[p] == -1) {
                L[p] = i;
                P[i] = p;
                return;
            }
            insert(insert, L[p], i);
        }
    };
    for (int i = 1; i < N; i++) {
        cin >> A[i];
        A[i]--;
        insert(insert, A[0], A[i]);
    }

    vector<int> B(N, -1), C(N, -1);
    auto solve = [&] (auto solve, int a, int depth) -> int {
        int ans = 0;
        if (R[a] != -1) {
            ans += solve(solve, R[a], depth + 1);
        }
        if (L[a] != -1) {
            ans += solve(solve, L[a], depth + 1);
        }
        B[a] = depth;
        C[a] = ans;
        return ans + 1;
    };
    solve(solve, A[0], 0);
    for (int i: A) cout << B[i] << ' ';
    cout << endl;
    for (int i: A) cout << C[i] << ' ';
    cout << endl;
    return 0;
}
0