結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2019-09-11 16:43:12 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 2,236 bytes |
コンパイル時間 | 2,077 ms |
コンパイル使用メモリ | 173,640 KB |
実行使用メモリ | 21,376 KB |
最終ジャッジ日時 | 2024-10-14 02:00:34 |
合計ジャッジ時間 | 3,073 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>using namespace std;using ll = long long;using VI = vector<int>;using VL = vector<ll>;#define FOR(i,a,n) for(int (i)=(a);(i)<(n);(i)++)#define eFOR(i,a,n) for(int (i)=(a);(i)<=(n);(i)++)#define rFOR(i,a,n) for(int (i)=(n)-1;(i)>=(a);(i)--)#define erFOR(i,a,n) for(int (i)=(n);(i)>=(a);(i)--)#define SORT(i) sort((i).begin(),(i).end())#define rSORT(i,a) sort((i).begin(),(i).end(),(a))#define all(i) (i).begin(),(i).end()constexpr ll INF = 1000000000;constexpr ll LLINF = 1LL << 60;constexpr ll mod = 1000000007;constexpr ll MOD = 998244353;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; }inline void init() { cin.tie(nullptr); cout.tie(nullptr); cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(15); }template<class V> class BIT {int n = 0; vector<V> bit;#define def 0public:BIT() {} // [L, R) 半開区間・0-indexedBIT(int _n) { init(_n); }void init(int _n) { n = 1; while (n < _n)n *= 2; bit.resize(n, def); }V operator[](int e) { V s = 0; e++; while (e) s += bit[e - 1], e -= e & -e; return s; }void add(int e, V v) { e++; while (e <= n) bit[e - 1] += v, e += e & -e; }int lower_bound(V val) {V tv = 0; int i, ent = 0; for (i = n - 1; i >= 0; i--)if (tv + bit[ent + (1 << i) - 1] <= val)tv += bit[ent + (1 << i) - 1], ent += (1 << i); return ent;}V sum(int L, int R) {assert(0 <= L); assert(R <= n); assert(L <= R);V res = 0; if (R) res += operator[](R - 1); if (L) res -= operator[](L - 1); return res;}V sum(int R) { return sum(0, R); }void clear() { bit.clear(); }void resize(int _n) { bit.clear(); init(_n); }int size() { return n; }};BIT<int> bit;vector<VI> edge;ll ans;void dfs(int i) {ans += bit.sum(i);bit.add(i, 1);for (int j : edge[i])dfs(j);bit.add(i, -1);}int main() {init();int n;cin >> n;edge.resize(n);bit.resize(n);int in;FOR(i, 1, n) {cin >> in;edge[in].push_back(i);}dfs(0);cout << ans << "\n";}