結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2018-12-25 00:04:35 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 121 ms / 2,000 ms |
コード長 | 675 bytes |
コンパイル時間 | 539 ms |
コンパイル使用メモリ | 62,684 KB |
実行使用メモリ | 21,352 KB |
最終ジャッジ日時 | 2024-10-14 01:50:53 |
合計ジャッジ時間 | 2,271 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge3 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <iostream>#include <algorithm>#include <vector>using namespace std;int n;vector<int> g[200000];int bit[200001];long long ans;void update(int k, int v) {for (int i = k + 1; i <= 200000; i += i & -i) {bit[i] += v;}}int query(int k) {int res = 0;for (int i = k; i > 0; i -= i & -i) {res += bit[i];}return res;}void dfs(int u) {ans += query(u);update(u, 1);for (int v : g[u]) {dfs(v);}update(u, -1);}int main() {cin >> n;for (int i = 1; i < n; i++) {int a;cin >> a;g[a].push_back(i);}dfs(0);cout << ans << endl;}