結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2021-05-23 15:07:30 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 174 ms / 2,000 ms |
コード長 | 2,912 bytes |
コンパイル時間 | 4,434 ms |
コンパイル使用メモリ | 256,272 KB |
最終ジャッジ日時 | 2025-01-21 17:44:31 |
ジャッジサーバーID (参考情報) |
judge2 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
#include <bits/stdc++.h>#define M_PI 3.14159265358979323846 // piusing namespace std;typedef long long ll;typedef unsigned long long ull;typedef pair<ll, ll> P;typedef tuple<ll, ll, ll> t3;typedef tuple<ll, ll, ll, ll> t4;#define rep(a,n) for(ll a = 0;a < n;a++)#define repi(a,b,n) for(ll a = b;a < n;a++)template<typename T>void chmax(T& reference, T value) {reference = max(reference, value);}template<typename T>void chmaxmap(map<T, T>& m, T key, T value) {if (m.count(key)) {chmax(m[key], value);}else {m[key] = value;}}template<typename T>void chmin(T& reference, T value) {reference = min(reference, value);}#include <atcoder/all>using namespace atcoder;typedef modint1000000007 mint;struct Point {ll x, y;bool operator <(const Point& p) const {return x < p.x || (x == p.x && y < p.y);}};struct ConvexHullRunner {typedef ll coord_t;typedef ll coord2_t;coord2_t cross(const Point& O, const Point& A, const Point& B){return (A.x - O.x) * (B.y - O.y) - (A.y - O.y) * (B.x - O.x);}vector<Point> convex_hull(vector<Point> P){size_t n = P.size(), k = 0;if (n <= 3) return P;vector<Point> H(2 * n);sort(P.begin(), P.end());for (size_t i = 0; i < n; ++i) {while (k >= 2 && cross(H[k - 2], H[k - 1], P[i]) <= 0) k--;H[k++] = P[i];}for (size_t i = n - 1, t = k + 1; i > 0; --i) {while (k >= t && cross(H[k - 2], H[k - 1], P[i - 1]) <= 0) k--;H[k++] = P[i - 1];}H.resize(k - 1);return H;}};ll gcd(ll a, ll b) { while (b) a %= b, swap(a, b); return abs(a); }static ll raw_cmb(ll n, ll k) {ll c = 1;for (int i = 1; i <= k; i++) {c *= (n + 1 - i);c /= i;}return c;}struct BIT {typedef ll input_t;vector<input_t> bit_;const long long n_;BIT(long long n) :n_(n) {bit_.resize(n + 1LL, 0);}input_t sum(int i) {input_t s = 0;while (i > 0) {s += bit_[i];i -= i & (-i);}return s;}void add(int i, input_t x) {while (i <= n_) {bit_[i] += x;i += (i & (-i));}}};int main() {int n;cin >> n;vector<vector<int>> g(n + 1);for (int i = 1; i < n;i++) {ll p;cin >> p;g[p + 1].push_back(i + 1);}BIT bit(n);ll sum = 0;function<void(ll, ll)> dfs = [&](ll current, ll parent) {sum += bit.sum(current);bit.add(current, 1);for (auto x : g[current]) {if (x == parent) continue;dfs(x, current);}bit.add(current, -1);};dfs(1, -1);cout << sum << endl;return 0;}