結果
問題 | No.778 クリスマスツリー |
ユーザー | kura197 |
提出日時 | 2019-11-05 00:49:37 |
言語 | C++11 (gcc 11.4.0) |
結果 |
AC
|
実行時間 | 188 ms / 2,000 ms |
コード長 | 1,720 bytes |
コンパイル時間 | 1,568 ms |
コンパイル使用メモリ | 164,388 KB |
実行使用メモリ | 29,464 KB |
最終ジャッジ日時 | 2024-10-14 02:00:44 |
合計ジャッジ時間 | 3,537 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge3 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 8 ms
11,428 KB |
testcase_01 | AC | 7 ms
11,392 KB |
testcase_02 | AC | 8 ms
11,420 KB |
testcase_03 | AC | 8 ms
11,508 KB |
testcase_04 | AC | 8 ms
11,380 KB |
testcase_05 | AC | 7 ms
11,392 KB |
testcase_06 | AC | 128 ms
29,340 KB |
testcase_07 | AC | 74 ms
12,320 KB |
testcase_08 | AC | 188 ms
19,940 KB |
testcase_09 | AC | 172 ms
14,720 KB |
testcase_10 | AC | 182 ms
14,720 KB |
testcase_11 | AC | 179 ms
14,740 KB |
testcase_12 | AC | 173 ms
14,592 KB |
testcase_13 | AC | 121 ms
14,592 KB |
testcase_14 | AC | 135 ms
29,464 KB |
ソースコード
#include <bits/stdc++.h> using namespace std; typedef long long ll; typedef unsigned long long ull; #define REP(i, n) for(int i=0; i<n; i++) #define REPi(i, a, b) for(int i=int(a); i<int(b); i++) template<class T>bool chmax(T &a, const T &b) { if (a<b) { a=b; return 1; } return 0; } template<class T>bool chmin(T &a, const T &b) { if (b<a) { a=b; return 1; } return 0; } const ll MOD = 1e9+7; class SegmentTree{ int n; vector<int> node; public: SegmentTree(vector<int> v){ n = 1; while(v.size() > n) n *= 2; node.resize(2*n-1); for(int i = 0; i < v.size(); i++) node[i+n-1] = v[i]; for(int i = n-1; i >= 0; i--) node[i] = node[2*i+1] + node[2*i+2]; } void add(int x, int t){ x += n-1; node[x] += t; while(x > 0){ x = (x-1) / 2; node[x] = node[2*x+1] + node[2*x+2]; } } int getsum(int a, int b, int k=0, int l=0, int r=-1){ if(r < 0) r = n; if(b <= l || r <= a) return 0; if(a <= l && r <= b) return node[k]; int rv = getsum(a, b, 2*k+1, l, (r+l)/2); int lv = getsum(a, b, 2*k+2, (r+l)/2, r); return rv+lv; } }; vector<int> G[200100]; ll ans; void dfs(int v, SegmentTree& tree){ ans += tree.getsum(0, v); for(auto&& next : G[v]){ tree.add(next, 1); dfs(next, tree); tree.add(next, -1); } } int main(){ int N; cin >> N; REP(i,N-1){ int a; cin >> a; G[a].push_back(i+1); } vector<int> A(200100); SegmentTree tree(A); tree.add(0, 1); dfs(0, tree); cout << ans << endl; return 0; }