結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2019-07-27 21:54:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 156 ms / 2,000 ms |
コード長 | 1,699 bytes |
コンパイル時間 | 694 ms |
コンパイル使用メモリ | 76,688 KB |
実行使用メモリ | 23,928 KB |
最終ジャッジ日時 | 2024-10-14 02:00:15 |
合計ジャッジ時間 | 2,479 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <algorithm>#include <iostream>#include <vector>using namespace std;template<typename Abel> struct BIT {const Abel UNITY_SUM = 0;vector<Abel> dat;BIT(int n) : dat(n, UNITY_SUM) { } // [0, n)inline void add(int i, Abel x) {while (i < dat.size()) { dat[i] += x; i |= i + 1; }}inline Abel sum(int i) { // [0, i]Abel res = UNITY_SUM;while (i >= 0) { res += dat[i]; i = (i & (i + 1)) - 1; }return res;}inline Abel sum(int a, int b) { return sum(b - 1) - sum(a - 1); } // [a, b)/* debug */Abel operator[](int i) { return sum(i, i + 1); }void dump() {for (int i = 0; i < dat.size(); ++i) cout << sum(i, i + 1) << ",";cout << endl;}};struct EulerTourOnVertex {vector<int> posL, posR;vector<vector<int>> g;int pos;EulerTourOnVertex(int n) : posL(n), posR(n), g(n) { }void add_edge(int u, int v) {g[u].emplace_back(v);g[v].emplace_back(u);}void dfs(int u, int p) {posL[u] = pos++;for (int v: g[u]) if (v != p) {dfs(v, u);pos++;}posR[u] = pos;}void build(int r = 0) {pos = 0;dfs(r, -1);}};int main() {int n; cin >> n;EulerTourOnVertex et(n);for (int u = 1; u < n; u++) {int p; cin >> p;et.add_edge(p, u);}et.build();BIT<int> bit(n * 2);long long cnt = 0;for (int i = n - 1; i >= 0; i--) {int left = et.posL[i];int right = et.posR[i];cnt += bit.sum(left, right + 1);bit.add(left, 1);}cout << cnt << endl;return 0;}