結果

問題 No.778 クリスマスツリー
ユーザー SSRS
提出日時 2022-04-23 16:12:27
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 115 ms / 2,000 ms
コード長 1,020 bytes
コンパイル時間 1,921 ms
コンパイル使用メモリ 199,308 KB
最終ジャッジ日時 2025-01-28 21:12:19
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <bits/stdc++.h>
using namespace std;
void dfs(vector<vector<int>> &c, vector<int> &L, vector<int> &R, int &t, int v = 0){
L[v] = t;
t++;
for (int w : c[v]){
dfs(c, L, R, t, w);
}
R[v] = t;
}
struct binary_indexed_tree{
int N;
vector<int> BIT;
binary_indexed_tree(int N): N(N), BIT(N + 1, 0){
}
void add(int i){
i++;
while (i <= N){
BIT[i]++;
i += i & -i;
}
}
int sum(int i){
int ans = 0;
while (i > 0){
ans += BIT[i];
i -= i & -i;
}
return ans;
}
int sum(int L, int R){
return sum(R) - sum(L);
}
};
int main(){
int N;
cin >> N;
vector<int> A(N, -1);
for (int i = 1; i < N; i++){
cin >> A[i];
}
vector<vector<int>> c(N);
for (int i = 1; i < N; i++){
c[A[i]].push_back(i);
}
vector<int> L(N), R(N);
int t = 0;
dfs(c, L, R, t);
binary_indexed_tree BIT(N);
long long ans = 0;
for (int i = N - 1; i >= 0; i--){
ans += BIT.sum(L[i], R[i]);
BIT.add(L[i]);
}
cout << ans << endl;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0