結果

問題 No.778 クリスマスツリー
ユーザー kakira9618
提出日時 2018-12-25 00:19:23
言語 C++11
(gcc 13.3.0)
結果
AC  
実行時間 582 ms / 2,000 ms
コード長 8,464 bytes
コンパイル時間 1,795 ms
コンパイル使用メモリ 189,192 KB
実行使用メモリ 61,052 KB
最終ジャッジ日時 2024-10-14 01:51:08
合計ジャッジ時間 6,759 ms
ジャッジサーバーID
(参考情報)
judge3 / judge2
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample AC * 3
other AC * 12
権限があれば一括ダウンロードができます

ソースコード

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

#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define mp make_pair
#define all(x) (x).begin(),(x).end()
#define rep(i,n) for(int i=0;i<(n);i++)
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int> pii;
constexpr int dx[] = {1, 0, -1, 0, 1, 1, -1, -1};
constexpr int dy[] = {0, -1, 0, 1, 1, -1, -1, 1};
template <typename T> ostream &operator<<(ostream &os, const vector<T> &vec){os << "["; for (const auto &v : vec) {os << v << ","; } os << "]";
    return os; }
template <typename T, typename U> ostream &operator<<(ostream &os, const pair<T, U> &p) {os << "(" << p.first << ", " << p.second << ")"; return os;}
// WaveletMatrix<T> T
// verified: https://codeforces.com/contest/1042/submission/43071856
// NA使O(N log max x) (max x)
// 1. rank(k, x): Akx
// 2. select(n, x): n(1-origin)x
// 3. QuantileRange(l, r, n): lrn(1-origin)
// 4. RankLessThan(l, r, x): lrx, x, x
// select(O(log N log max x))O(log max x)
// 使: T = long long, N = 2*10^5 20MB
// Ax
// usage:
// vector<int> A(N);
// WaveletMatrix<int> wm(A);
template<typename T>
struct WaveletMatrix {
// FID
// (O(N))
struct FID {
vector<uint32_t> bit;
vector<int> acc;
int N;
FID(vector<int> &bit_) {
N = bit_.size();
int N2 = (N >> 5) + 1;
bit.resize(N2);
for(int i = 0; i < N2; i++) {
for(int j = 0; j < 32; j++) {
if ((i << 5) + j < N) bit[i] |= bit_[(i << 5) + j] << j;
}
}
acc = vector<int>(N2);
for(int i = 0; i < N2 - 1; i++) {
acc[i + 1] = acc[i] + __builtin_popcount(bit[i]);
}
}
FID() {}
// rank: kx
// O(1)
inline int rank(int k, int x = 1) {
int n1 = acc[k >> 5] + __builtin_popcount(bit[k >> 5] & (uint32_t)(((1ULL << (k & 0x1f)) - 1)));
return x ? n1 : k - n1;
}
// select: nx
// O(log N)
inline int select(int n, int x = 1) {
int ng = 0, ok = N + 1;
while(ok - ng > 1) {
int c = (ok + ng) / 2;
if (rank(c, x) >= n) {
ok = c;
} else {
ng = c;
}
}
return ok;
}
inline int operator[](int k) {
return ((bit[k >> 5] >> (k & 0x1f)) & 1);
}
inline size_t size() {
return N;
}
};
vector<int> cntZero;
vector<FID> bits;
unordered_map<ll, int> pos;
int level;
ll mask;
// rank
// Akx
// O(log max x)
inline int rank(int k, T x) {
int now = k;
for(int j = level - 1; j >= 0; j--) {
if (x >> j & 1) {
now = cntZero[j] + bits[j].rank(now);
} else {
now = now - bits[j].rank(now);
}
}
return now - pos[x ^ mask];
}
// select:
// n(1-origin)x
// O(log N log max x)
inline int select(int n, T x) {
int now = pos[x ^ mask] + n;
for(int j = 0; j < level; j++) {
if (x >> j & 1) {
int w = now - cntZero[j];
now = bits[j].select(w);
} else {
now = bits[j].select(now, 0);
}
}
return now;
}
// QuantileRange
// lrn(1-origin)
//
// O(log max x)
inline pair<T, int> QuantileRange(int l, int r, int n) {
T ans = 0;
for(int j = level - 1; j >= 0; j--) {
ans <<= 1LL;
int nz = bits[j].rank(r, 0) - bits[j].rank(l, 0);
if (n > nz) {
n -= nz;
l = bits[j].rank(l, 1) + cntZero[j];
r = bits[j].rank(r, 1) + cntZero[j];
ans |= 1LL;
} else {
l = bits[j].rank(l, 0);
r = bits[j].rank(r, 0);
}
}
return {ans, l + n - pos[ans ^ mask]};
}
// RankLessThan
// lrx, x, x
// tuple<int, int, int> ret = wm.RankLessThan(0, N, x); int eq = get<0>(ret), less = get<1>(ret), greater = get<2>(ret);
// O(log max x)
inline tuple<int, int, int> RankLessThan(int l, int r, T x) {
T n_eq = 0, n_less = 0, n_greater = 0;
for(int j = level - 1; j >= 0; j--) {
if (x >> j & 1) {
n_less += bits[j].rank(r, 0) - bits[j].rank(l, 0);
l = bits[j].rank(l, 1) + cntZero[j];
r = bits[j].rank(r, 1) + cntZero[j];
} else {
n_greater += bits[j].rank(r, 1) - bits[j].rank(l, 1);
l = bits[j].rank(l, 0);
r = bits[j].rank(r, 0);
}
}
n_eq = r - l;
return make_tuple(n_eq, n_less, n_greater);
}
WaveletMatrix(vector<T> A_) : level(sizeof(T) * 8) {
cntZero.resize(level);
bits.resize(level);
vector<T> zero(A_.size());
vector<T> one(A_.size());
for(int j = level - 1; j >= 0; j--) {
int n0 = 0, n1 = 0;
vector<int> bit(A_.size());
int cnt = 0;
for(int i = 0; i < A_.size(); i++) {
if (A_[i] >> j & 1) {
one[n1++] = A_[i];
bit[i] = 1;
} else {
zero[n0++] = A_[i];
cnt++;
}
}
vector<T> newA(zero.begin(), zero.begin() + n0);
newA.insert(newA.end(), one.begin(), one.begin() + n1);
A_ = std::move(newA);
bits[j] = FID(bit);
cntZero[j] = cnt;
}
//reverse(bits.begin(), bits.end());
mask = random_device()();
for(int i = 0; i < A_.size(); i++) {
if (pos.find(A_[i]) == pos.end()) {
pos[A_[i] ^ mask] = i;
}
}
}
void show() {
cout << "cntZero: ";
for (int i = 0; i < cntZero.size(); i++) {
cout << cntZero[i] << ", ";
}
cout << endl;
cout << "bits: " << endl;
for (int j = 0; j < level; j++) {
for (int i = 0; i < bits[j].size(); i++) {
cout << bits[j][i] << ", ";
}
cout << endl;
}
cout << endl;
}
};
int now = 0;
vector<int> A;
map<int, pii> B;
void dfs(int v, vector<vector<int>> &G) {
int s = now++;
A.push_back(v);
for (int i = 0; i < G[v].size(); i++) {
dfs(G[v][i], G);
}
int t = now++;
A.push_back(v);
B[v] = {s, t};
}
void solve() {
int N;
cin >> N;
vector<vector<int>> G(N);
for (int i = 0; i < N - 1; i++) {
int p; cin >> p;
G[p].push_back(i + 1);
}
dfs(0, G);
WaveletMatrix<int> wm(A);
ll ans = 0;
for(int i = 0; i < N; i++) {
int s = B[i].first;
int t = B[i].second + 1;
ll cnt = get<2>(wm.RankLessThan(s, t, i));
ans += cnt / 2;
}
cout << ans << endl;
}
int main() {
std::cin.tie(0);
std::ios::sync_with_stdio(false);
cout.setf(ios::fixed);
cout.precision(16);
solve();
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0