結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2018-12-25 00:05:07 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 70 ms / 2,000 ms |
コード長 | 628 bytes |
コンパイル時間 | 450 ms |
コンパイル使用メモリ | 48,768 KB |
実行使用メモリ | 22,004 KB |
最終ジャッジ日時 | 2024-10-14 01:50:46 |
合計ジャッジ時間 | 1,598 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <stdio.h>#include <vector>using namespace std;int B[200200];int N,P[200200];vector<int> G[200200];long long ans;void in(int x, int p){while (x <= N){B[x] += p;x += x & (-x);}}int out(int x){int r = 0;while (x){r += B[x];x -= x & (-x);}return r;}void go(int x){ans += out(x+1);in(x+1,1);for (auto y : G[x]) go(y);in(x+1,-1);}int main(){scanf ("%d",&N);for (int i=1;i<N;i++){scanf ("%d",&P[i]);G[P[i]].push_back(i);}go(0);printf ("%lld\n",ans);return 0;}