結果
問題 | No.778 クリスマスツリー |
ユーザー | Fukucchi |
提出日時 | 2021-10-20 12:45:30 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 864 ms / 2,000 ms |
コード長 | 13,825 bytes |
コンパイル時間 | 2,066 ms |
コンパイル使用メモリ | 145,296 KB |
実行使用メモリ | 103,044 KB |
最終ジャッジ日時 | 2024-09-20 06:32:50 |
合計ジャッジ時間 | 8,674 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge1 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 2 ms
5,248 KB |
testcase_01 | AC | 1 ms
5,376 KB |
testcase_02 | AC | 2 ms
5,376 KB |
testcase_03 | AC | 2 ms
5,376 KB |
testcase_04 | AC | 2 ms
5,376 KB |
testcase_05 | AC | 2 ms
5,376 KB |
testcase_06 | AC | 135 ms
59,500 KB |
testcase_07 | AC | 106 ms
36,028 KB |
testcase_08 | AC | 486 ms
51,624 KB |
testcase_09 | AC | 833 ms
76,344 KB |
testcase_10 | AC | 864 ms
78,196 KB |
testcase_11 | AC | 859 ms
77,652 KB |
testcase_12 | AC | 801 ms
73,332 KB |
testcase_13 | AC | 817 ms
103,044 KB |
testcase_14 | AC | 133 ms
59,504 KB |
ソースコード
/* #region header */ #pragma GCC optimize("O3") //コンパイラ最適化用 #ifdef LOCAL #define _GLIBCXX_DEBUG //配列に[]でアクセス時のエラー表示 #endif #define _USE_MATH_DEFINES #include <algorithm> //sort,二分探索,など #include <bitset> //固定長bit集合 // #include <boost/multiprecision/cpp_dec_float.hpp> // #include <boost/multiprecision/cpp_int.hpp> #include <cassert> //assert(p)で,not pのときにエラー #include <cctype> #include <chrono> //実行時間計測 #include <climits> #include <cmath> //pow,logなど #include <complex> //複素数 #include <cstdio> #include <cstring> #include <deque> #include <functional> //sortのgreater #include <iomanip> //setprecision(浮動小数点の出力の誤差) #include <ios> // std::left, std::right #include <iostream> //入出力 #include <iterator> //集合演算(積集合,和集合,差集合など) #include <map> #include <numeric> //iota(整数列の生成),gcdとlcm,accumulate #include <queue> #include <random> #include <set> #include <stack> #include <string> #include <unordered_map> #include <unordered_set> #include <utility> //pair #include <vector> using namespace std; typedef long long LL; typedef long double LD; #define ALL(x) x.begin(), x.end() const long long INF = numeric_limits<long long>::max() / 4; const int MOD = 1e9 + 7; // const int MOD=998244353; //略記 #define FF first #define SS second #define int long long #define stoi stoll #define LD long double #define PII pair<int, int> #define PB push_back #define EB emplace_back #define MP make_pair #define SZ(x) (int)((x).size()) #define VB vector<bool> #define VVB vector<vector<bool>> #define VI vector<int> #define VVI vector<vector<int>> #define REP(i, n) for (int i = 0; i < (int)(n); i++) #define REPD(i, n) for (int i = (int)(n) - (int)1; i >= 0; i--) #define FOR(i, a, b) for (int i = a; i < (int)(b); i++) #define FORD(i, a, b) for (int i = (int)(b) - (int)1; i >= (int)a; i--) const int dx[4] = {0, 1, 0, -1}, dy[4] = {-1, 0, 1, 0}; const int Dx[8] = {0, 1, 1, 1, 0, -1, -1, -1}, Dy[8] = {-1, -1, 0, 1, 1, 1, 0, -1}; int in() { int x; cin >> x; return x; } // https://qiita.com/Lily0727K/items/06cb1d6da8a436369eed#c%E3%81%A7%E3%81%AE%E5%AE%9F%E8%A3%85 void print() { cout << "\n"; } template <class Head, class... Tail> void print(Head &&head, Tail &&...tail) { cout << head; if (sizeof...(tail) != 0) cout << " "; print(forward<Tail>(tail)...); } template <class T> void print(vector<T> &vec) { for (auto &a : vec) { cout << a; if (&a != &vec.back()) cout << " "; } cout << "\n"; } template <class T> void print(set<T> &set) { for (auto &a : set) { cout << a << " "; } cout << "\n"; } template <class T> void print(vector<vector<T>> &df) { for (auto &vec : df) { print(vec); } } // debug macro // https://atcoder.jp/contests/abc202/submissions/22815715 namespace debugger { template <class T> void view(const std::vector<T> &a) { std::cerr << "{ "; for (const auto &v : a) { std::cerr << v << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const std::vector<std::vector<T>> &a) { std::cerr << "{\n"; for (const auto &v : a) { std::cerr << "\t"; view(v); std::cerr << "\n"; } std::cerr << "}"; } template <class T, class U> void view(const std::vector<std::pair<T, U>> &a) { std::cerr << "{\n"; for (const auto &p : a) std::cerr << "\t(" << p.first << ", " << p.second << ")\n"; std::cerr << "}"; } template <class T, class U> void view(const std::map<T, U> &m) { std::cerr << "{\n"; for (const auto &p : m) std::cerr << "\t[" << p.first << "] : " << p.second << "\n"; std::cerr << "}"; } template <class T, class U> void view(const std::pair<T, U> &p) { std::cerr << "(" << p.first << ", " << p.second << ")"; } template <class T> void view(const std::set<T> &s) { std::cerr << "{ "; for (auto &v : s) { view(v); std::cerr << ", "; } std::cerr << "\b\b }"; } template <class T> void view(const T &e) { std::cerr << e; } } // namespace debugger #ifdef LOCAL void debug_out() {} template <typename Head, typename... Tail> void debug_out(Head H, Tail... T) { debugger::view(H); std::cerr << ", "; debug_out(T...); } #define debug(...) \ do { \ std::cerr << __LINE__ << " [" << #__VA_ARGS__ << "] : ["; \ debug_out(__VA_ARGS__); \ std::cerr << "\b\b]\n"; \ } while (false) #else #define debug(...) (void(0)) #endif long long power(long long x, long long n) { // O(logn) // https://algo-logic.info/calc-pow/#toc_id_1_2 long long ret = 1; while (n > 0) { if (n & 1) ret *= x; // n の最下位bitが 1 ならば x^(2^i) をかける x *= x; n >>= 1; // n を1bit 左にずらす } return ret; } // @brief nCr. O(r log n)。あるいは前処理 O(n), 本処理 O(1)で求められる modint // の bc を検討。 int comb(int n, int r) { // https://www.geeksforgeeks.org/program-to-calculate-the-value-of-ncr-efficiently/ if (n < r) return 0; // p holds the value of n*(n-1)*(n-2)..., // k holds the value of r*(r-1)... long long p = 1, k = 1; // C(n, r) == C(n, n-r), // choosing the smaller value if (n - r < r) r = n - r; if (r != 0) { while (r) { p *= n; k *= r; // gcd of p, k long long m = __gcd(p, k); // dividing by gcd, to simplify // product division by their gcd // saves from the overflow p /= m; k /= m; n--; r--; } // k should be simplified to 1 // as C(n, r) is a natural number // (denominator should be 1 ) . } else p = 1; // if our approach is correct p = ans and k =1 return p; } // MOD void add(long long &a, long long b) { a += b; if (a >= MOD) a -= MOD; } template <class T> inline bool chmin(T &a, T b) { if (a > b) { a = b; return true; } return false; } template <class T> inline bool chmax(T &a, T b) { if (a < b) { a = b; return true; } return false; } // 負数も含む丸め long long ceildiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return (a + b - 1) / b; else return a / b; } long long floordiv(long long a, long long b) { if (b < 0) a = -a, b = -b; if (a >= 0) return a / b; else return (a - b + 1) / b; } long long floorsqrt(long long x) { assert(x >= 0); long long ok = 0; long long ng = 1; while (ng * ng <= x) ng <<= 1; while (ng - ok > 1) { long long mid = (ng + ok) >> 1; if (mid * mid <= x) ok = mid; else ng = mid; } return ok; } // @brief a^n mod mod long long modpower(long long a, long long n, long long mod) { long long res = 1; while (n > 0) { if (n & 1) res = res * a % mod; a = a * a % mod; n >>= 1; } return res; } // @brief s が c を含むか template <class T> bool contain(const std::string &s, const T &c) { return s.find(c) != std::string::npos; } __attribute__((constructor)) void faster_io() { ios_base::sync_with_stdio(false); cin.tie(nullptr); cerr.tie(nullptr); } /* #endregion */ using Graph = vector<vector<int>>; int ans = 0; template <typename T> class RBST { private: struct node { T val; node *left, *right; int st_size; // 部分木のサイズ node() {} node(T v) : val(v), left(nullptr), right(nullptr), st_size(1) {} ~node() { delete left; delete right; } }; node *root; using pnn = pair<node *, node *>; int size(node *t) { return t ? t->st_size : 0; } node *update(node *t) { node *l = t->left; node *r = t->right; t->st_size = size(l) + size(r) + 1; return t; } unsigned rnd() { static unsigned x = 123456789, y = 362436069, z = 521288629, w = 86675123; unsigned t = (x ^ (x << 11)); x = y, y = z, z = w; return (w = (w ^ (w >> 19)) ^ (t ^ (t >> 8))); } node *merge(node *l, node *r) { if (!l || !r) return (!l) ? r : l; if (rnd() % (size(l) + size(r)) < (unsigned)size(l)) { l->right = merge(l->right, r); return update(l); } else { r->left = merge(l, r->left); return update(r); } } pnn split(node *t, int k) { //木のサイズが(k,n-k)となるように分割する if (!t) return pnn(nullptr, nullptr); if (k <= size(t->left)) { pnn s = split(t->left, k); t->left = s.second; return pnn(s.first, update(t)); } else { pnn s = split(t->right, k - size(t->left) - 1); t->right = s.first; return pnn(update(t), s.second); } } int lower_bound(node *t, const T k) { if (!t) return 0; if (t->val < k) { return size(t->left) + lower_bound(t->right, k) + 1; } else { return lower_bound(t->left, k); } } void lower_value(node *t, const T k, T &res) { if (!t) return; if (t->val < k) { lower_value(t->right, k, res); } else { lower_value(t->left, k, res = t->val); } } int upper_bound(node *t, const T k) { if (!t) return 0; if (t->val <= k) { return size(t->left) + upper_bound(t->right, k) + 1; } else { return upper_bound(t->left, k); } } void upper_value(node *t, const T k, T &res) { if (!t) return; if (t->val <= k) { upper_value(t->right, k, res); } else { upper_value(t->left, k, res = t->val); } } T get(node *t, int k) { if (!t) assert(false); int s = size(t->left); if (s > k) return get(t->left, k); else if (s < k) return get(t->right, k - s - 1); else return t->val; } node *insert(node *t, int k, node *u) { pnn s = split(t, k); return merge(merge(s.first, u), s.second); } pnn erase(node *t, int k) { pnn sr = split(t, k + 1); pnn sl = split(sr.first, k); return pnn(merge(sl.first, sr.second), sl.second); } public: RBST() : root(nullptr) {} // k以上の数の最小インデックス int lower_bound(const T k) { return lower_bound(root, k); } // k以上の最小の数 T lower_value(const T k) { T res = numeric_limits<T>::max(); lower_value(root, k, res); return res; } // kを超える数の最小インデックス int upper_bound(const T k) { return upper_bound(root, k); } // kを超える最小の数 T upper_value(const T k) { T res = numeric_limits<T>::max(); upper_value(root, k, res); return res; } //値valを挿入 void insert(T val) { root = insert(root, upper_bound(val), new node(val)); } //値valを削除 void erase(T val) { node *p; tie(root, p) = erase(root, lower_bound(val)); p->left = p->right = nullptr; delete p; } // k番目の値を返す T get(int k) { return get(root, k); } void print() { int sz = size(root); REP(i, sz) cout << get(i) << " "; cout << "\n"; } int size() { return size(root); } // a, b をマージする.a に全要素が入り,b が空になる. RBST<int> merge_tech(RBST<int> &a, RBST<int> &b) { if (a.size() < b.size()) { swap(a, b); } REP(i, b.size()) { a.insert(b.get(i)); } return a; } }; // https://kopricky.github.io/code/BinarySearchTree/rbst_set.html /* signed main() { RBST<PII> rs; REP(ni, n) { rs.insert(MP(X[ni], ni)); if (ni + 1 >= k) print(rs.get(k - 1).SS + 1); } return 0; } */ vector<RBST<int>> dp; RBST<int> rs; // 木上の探索 // v: 現在探索中の頂点、p: v の親 (v が根のときは -1) void dfs(const Graph &G, int v, int p) { for (auto nv : G[v]) { if (nv == p) continue; // nv が親 p だったらダメ dfs(G, nv, v); // v は新たに nv の親になります } dp[v].insert(v); for (auto c : G[v]) { if (c == p) continue; dp[v] = rs.merge_tech(dp[v], dp[c]); // REP(ni, SZ(dp[c])) { dp[v].insert(dp[c].get(ni)); } } // print("root", v); // dp[v].print(); int idx = dp[v].upper_bound(v); ans += dp[v].size() - idx; } signed main() { // 頂点数 (木なので辺数は N-1 で確定) int n; cin >> n; // グラフ入力受取 Graph G(n); for (int i = 0; i < n - 1; ++i) { int v; cin >> v; G[i + 1].push_back(v); G[v].push_back(i + 1); } debug(G); // exit(0); dp.resize(n); // 探索 int root = 0; // 仮に頂点 0 を根とする dfs(G, root, -1); print(ans); }