結果

問題 No.778 クリスマスツリー
ユーザー commy
提出日時 2020-04-10 00:55:15
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 282 ms / 2,000 ms
コード長 2,916 bytes
コンパイル時間 1,329 ms
コンパイル使用メモリ 98,020 KB
最終ジャッジ日時 2025-01-09 15:35:30
ジャッジサーバーID
(参考情報)
judge1 / judge5
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

#include <iostream>
#include <vector>
#include <algorithm>
#include <string>
#include <numeric>
#include <utility>
#include <tuple>
#define REP(i, a, b) for (int i = int(a); i < int(b); i++)
using namespace std;
using ll = long long int;
using P = pair<int, int>;
// clang-format off
#ifdef _DEBUG_
#define dump(...) do{ cerr << __LINE__ << ":\t" << #__VA_ARGS__ << " = "; PPPPP(__VA_ARGS__); cerr << endl; } while(false)
template<typename T> void PPPPP(T t) { cerr << t; }
template<typename T, typename... S> void PPPPP(T t, S... s) { cerr << t << ", "; PPPPP(s...); }
#else
#define dump(...) do{ } while(false)
#endif
template<typename T> vector<T> make_v(size_t a, T b) { return vector<T>(a, b); }
template<typename... Ts> auto make_v(size_t a, Ts... ts) { return vector<decltype(make_v(ts...))>(a, make_v(ts...)); }
template<typename T> bool chmin(T &a, T b) { if (a > b) {a = b; return true; } return false; }
template<typename T> bool chmax(T &a, T b) { if (a < b) {a = b; return true; } return false; }
template<typename T> void print(T a) { cout << a << endl; }
template<typename T, typename... Ts> void print(T a, Ts... ts) { cout << a << ' '; print(ts...); }
template<typename T> istream &operator,(istream &in, T &t) { return in >> t; }
// clang-format on
#include <functional>
template<typename T>
class SegmentTreeOneAll {
using Func = function<T(T, T)>;
public:
vector<T> data;
int n;
T init;
Func update_func;
Func query_func;
SegmentTreeOneAll(int _n, T _init, Func up, Func qu) {
init = _init;
update_func = up;
query_func = qu;
for (n = 1; n < _n; n *= 2)
;
data.resize(2 * n - 1, init);
}
void update(int pos, T val) {
pos += n - 1;
data[pos] = update_func(data[pos], val);
while (pos > 0) {
pos = (pos - 1) / 2;
data[pos] = query_func(data[2 * pos + 1], data[2 * pos + 2]);
}
}
T query(int l, int r) {
T resL = init, resR = init;
for (l += n - 1, r += n - 1; l < r; l = l / 2, r = (r - 1) / 2) {
if (!(l & 1)) {
resL = query_func(resL, data[l]);
}
if (!(r & 1)) {
resR = query_func(data[r - 1], resR);
}
}
return query_func(resL, resR);
}
};
int main() {
cin.tie(nullptr);
ios::sync_with_stdio(false);
int n;
cin, n;
vector<vector<int>> T(n);
REP(i, 1, n) {
int a;
cin, a;
T[a].push_back(i);
}
auto SUM = [](ll a, ll b) {
return a + b;
};
SegmentTreeOneAll<ll> seg(n, 0, SUM, SUM);
function<ll(int)> dfs = [&](int v) {
ll res = seg.query(0, v);
seg.update(v, 1);
for (auto vv : T[v]) {
res += dfs(vv);
}
seg.update(v, -1);
return res;
};
cout << dfs(0) << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0