結果

問題 No.3134 二分探索木
コンテスト
ユーザー tobbie
提出日時 2025-05-30 09:42:40
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,286 bytes
コンパイル時間 1,966 ms
コンパイル使用メモリ 199,160 KB
実行使用メモリ 14,112 KB
最終ジャッジ日時 2025-05-30 09:42:48
合計ジャッジ時間 7,247 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge2
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 5
other AC * 8 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

#define rep(i, n) for (int i = 0; i < (int)n; i++)

struct Node {
  int left;
  int right;
  Node(int left, int right) : left(left), right(right) {}
};

void insert(vector<struct Node> &node, int x, int y) {
  if (x == y)
    return;
  if (y < x) {
    if (node[x].left == -1) {
      node[x].left = y;
      return;
    } else {
      x = node[x].left;
      insert(node, x, y);
    }
  } else {
    if (node[x].right == -1) {
      node[x].right = y;
      return;
    } else {
      x = node[x].right;
      insert(node, x, y);
    }
  }
  return;
}

int main() {
  int n;
  cin >> n;
  vector<struct Node> node(n, {-1, -1});
  vector<int> a(n), ainv(n);
  rep(i, n) {
    cin >> a[i]; a[i]--;
    insert(node, a[0], a[i]);
    ainv[a[i]] = i;
  }
  vector<int> b(n), c(n);
  auto dfs = [&](auto dfs, int x, int d) {
    if (x < 0)
      return 0;
    b[ainv[x]] = d;
    int r = 0;
    r += dfs(dfs, node[x].right, d + 1);
    r += dfs(dfs, node[x].left, d + 1);
    c[ainv[x]] = r;
    return r + 1;
  };
  dfs(dfs, a[0], 0);
  rep(i, n) {
    cout << b[i];
    if (i < n-1) cout << " ";
    else         cout << endl;
  }
  rep(i, n) {
    cout << c[i];
    if (i < n-1) cout << " ";
    else         cout << endl;
  }
  return 0;
}
0