結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2019-06-22 16:32:28 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 133 ms / 2,000 ms |
コード長 | 1,274 bytes |
コンパイル時間 | 1,592 ms |
コンパイル使用メモリ | 171,828 KB |
実行使用メモリ | 25,088 KB |
最終ジャッジ日時 | 2024-10-14 01:59:27 |
合計ジャッジ時間 | 3,340 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;template<typename T>struct BIT {int n;vector<T> dat;BIT(int n=0){initialize(n);}void initialize(int nin){n = nin;dat.resize(n, 0);}T sum(int i){T s = 0;while(i >= 0){s += dat[i];i = (i & (i+1)) - 1;}return s;}T sum_between(int i, int j){return sum(j) - sum(i-1);}void plus(int i, T x){while(i < n){dat[i] += x;i |= i+1;}}// a[0]+...+a[ret] >= xint lower_bound(T x){int ret = -1;int k = 1;while(2*k <= n) k <<= 1;for( ;k>0; k>>=1){if(ret+k < n && dat[ret+k] < x){x -= dat[ret+k];ret += k;}}return ret + 1;}};vector<int> child[200000];BIT<int64_t> bit(200000);int64_t ans = 0;void dfs(int i){ans += bit.sum(i-1);bit.plus(i, 1);for(int j : child[i]) dfs(j);bit.plus(i, -1);}int main(){int N;cin >> N;for(int i=1; i<N; i++){int a;cin >> a;child[a].push_back(i);}dfs(0);cout << ans << endl;return 0;}