結果

問題 No.778 クリスマスツリー
ユーザー naribownaribow
提出日時 2020-09-22 10:27:05
言語 C++14
(gcc 12.3.0 + boost 1.83.0)
結果
AC  
実行時間 168 ms / 2,000 ms
コード長 2,363 bytes
コンパイル時間 1,756 ms
コンパイル使用メモリ 170,376 KB
実行使用メモリ 32,148 KB
最終ジャッジ日時 2023-09-08 04:02:36
合計ジャッジ時間 4,251 ms
ジャッジサーバーID
（参考情報） 		judge13 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 4 ms
9,144 KB
testcase_01 AC 5 ms
9,152 KB
testcase_02 AC 5 ms
9,040 KB
testcase_03 AC 5 ms
9,140 KB
testcase_04 AC 5 ms
9,144 KB
testcase_05 AC 4 ms
9,040 KB
testcase_06 AC 101 ms
32,148 KB
testcase_07 AC 57 ms
17,080 KB
testcase_08 AC 168 ms
24,152 KB
testcase_09 AC 150 ms
16,508 KB
testcase_10 AC 148 ms
16,452 KB
testcase_11 AC 149 ms
16,448 KB
testcase_12 AC 141 ms
16,392 KB
testcase_13 AC 90 ms
16,396 KB
testcase_14 AC 99 ms
32,024 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const double pi=3.141592653589793;
typedef unsigned long long ull;
typedef long double ldouble;
const ll INF=1e18;
#define rep(i, n) for(ll i = 0; i < (ll)(n); i++)
#define rep2(i, s, n) for (ll i = (s); i < (ll)(n); i++)
template<class T> inline bool chmax(T& a, T b) { if (a < b) { a = b; return 1; } return 0; }
template<class T> inline bool chmin(T& a, T b) { if (a > b) { a = b; return 1; } return 0; }

class BIT {
public:
    ll n; //データの長さ
    vector<ll> bit; //データの格納先
    BIT(ll n):n(n),bit(n+1,0){} //コンストラクタ

    //k & -kはLSB

    //bit_iにxをO(log(n))で加算する
    void add(ll i,ll x){
        if(i==0) return;
        for(ll k=i;k<=n;k+=(k & -k)){
            bit[k]+=x;
        }
    }

    //bit_1 + bit_2 + …  + bit_n をO(log(n))で求める
    ll sum(ll i){
        ll s=0;
        if(i==0) return s;
        for(ll k=i;k>0;k-=(k & -k)){
            s+=bit[k];
        }
        return s;
    }

    //a_1 + a_2 + … + a_i >= x となるような最小のiを求める(a_k >= 0)
    //xが0以下の場合は該当するものなし→0を返す
    ll lower_bound(ll x){
        if(x<=0){
            return 0;
        }else{
            ll i=0;ll r=1;
            //最大としてありうる区間の長さを取得する
            //n以下の最小の二乗のべき(BITで管理する数列の区間で最大のもの)を求める
            while(r<n) r=r<<1;
            //区間の長さは調べるごとに半分になる
            for(int len=r;len>0;len=len>>1) {
                //その区間を採用する場合
                if(i+len<n && bit[i+len]<x){
                    x-=bit[i+len];
                    i+=len;
                }
            }
            return i+1;
        }
    }
};

vector<vector<int> > G(200010);
BIT bit(200010);
ll ans = 0;

void dfs (int cu, int pa) {
    bit.add(cu, 1);
    ans += bit.sum(cu);
    rep(i, G[cu].size()) {
        int to = G[cu][i];
        if(to != pa) {
            dfs(to, cu);
        }
    }

    bit.add(cu, -1);
    return;
}

int main() {
    int n;
    cin >> n;
    vector<int> a(n);
    rep2(i, 1, n) {
        cin >> a[i];
        G[a[i]].push_back(i);
        G[i].push_back(a[i]);
    }
    
    dfs(0, -1);
    cout << ans << endl;
}
0