結果
問題 |
No.778 クリスマスツリー
|
ユーザー |
|
提出日時 | 2025-10-08 21:50:22 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 154 ms / 2,000 ms |
コード長 | 2,895 bytes |
コンパイル時間 | 5,949 ms |
コンパイル使用メモリ | 334,072 KB |
実行使用メモリ | 31,752 KB |
最終ジャッジ日時 | 2025-10-08 21:50:33 |
合計ジャッジ時間 | 8,660 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
// 基本 #include <bits/stdc++.h> #include <atcoder/all> using namespace std; using namespace atcoder; // 型名の省略 using ll = long long; template <class T> using vc = vector<T>; template <class T> using vvc = vector<vc<T>>; template <class T> using vvvc = vector<vvc<T>>; template <class T> using vvvvc = vector<vvvc<T>>; template <class T> using vvvvvc = vector<vvvvc<T>>; template <class T> using pq = priority_queue<T>; template <class T> using pqg = priority_queue<T, vector<T>, greater<T>>; // 定数 constexpr long long MOD = 1000000007LL; template <class T> constexpr T INF = 0; template <> constexpr int INF<int> = 1001001001; template <> constexpr long long INF<long long> = 1LL << 61; template <> constexpr double INF<double> = INF<long long>; template <> constexpr long double INF<long double> = INF<long long>; // 便利関数 // 入出力処理 template <class... T> void input(T &...a) { (cin >> ... >> a); } void print() { cout << '\n'; } template <class T, class... Ts> void print(const T &a, const Ts &...b) { cout << a; (cout << ... << (cout << ' ', b)); cout << '\n'; } // 繰り返し処理 #define overload4(a, b, c, d, e, ...) e #define rep1(a) for (int i = 0; i < a; i++) #define rep2(i, a) for (int i = 0; i < a; i++) #define rep3(i, a, b) for (int i = a; i < b; i++) #define rep4(i, a, b, c) for (int i = a; i < b; i += c) #define rep(...) overload4(__VA_ARGS__, rep4, rep3, rep2, rep1)(__VA_ARGS__) // 配列処理 template <class T> bool operator==(const vector<T> &a, const vector<T> &b) { return (a.size() == b.size()) && equal(a.cbegin(), a.cend(), b.cbegin()); } template <class T> bool operator!=(const vector<T> &a, const vector<T> &b) { return !(a == b); } // 最小・最大処理 template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <class... Args> inline auto all_max(Args... args) { return max(initializer_list<common_type_t<Args...>>{args...}); } template <class... Args> inline auto all_min(Args... args) { return min(initializer_list<common_type_t<Args...>>{args...}); } // 追加ライブラリ using S = int; S op(S l, S r) { return l + r; } S e() { return 0; } /// ここからコードを書く int main() { cin.tie(0); int n; input(n); vvc<int> a(n); rep(i, n - 1) { int at; input(at); a[at].push_back(i + 1); } segtree<S, op, e> seg(n); ll ans = 0; auto dfs = [&](auto self, int cu) -> void { ans += seg.prod(0, cu); seg.set(cu, 1); for (int ne : a[cu]) { self(self, ne); } seg.set(cu, 0); }; dfs(dfs, 0); print(ans); return 0; }