結果
問題 | No.778 クリスマスツリー |
ユーザー |
|
提出日時 | 2018-12-29 12:52:49 |
言語 | D (dmd 2.109.1) |
結果 |
AC
|
実行時間 | 125 ms / 2,000 ms |
コード長 | 2,019 bytes |
コンパイル時間 | 1,029 ms |
コンパイル使用メモリ | 109,252 KB |
実行使用メモリ | 45,020 KB |
最終ジャッジ日時 | 2024-06-13 02:25:54 |
合計ジャッジ時間 | 2,452 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
ソースコード
import std.stdio, std.string, std.conv;import std.range, std.algorithm, std.array, std.typecons, std.container;import std.math, std.numeric, core.bitop;void main() {int n;scan(n);auto a = readln.split.to!(int[]);long ans = solve(n, a);ans.writeln;}long solve(int n, int[] a) {auto ch = new int[][](n, 0);foreach (i, ai; a) {ch[ai] ~= i.to!int + 1;}int[] et;auto begin = new int[](n);auto end = new int[](n);void dfs(int v) {begin[v] = et.length.to!int;et ~= v;foreach (u ; ch[v]) {dfs(u);et ~= v;}end[v] = et.length.to!int;}dfs(0);debug {stderr.writeln(et);stderr.writeln(begin);stderr.writeln(end);}auto bit = FenwickTree!(int)(2*n);long ans;foreach_reverse (i ; 0 .. n) {int cnt = bit.sum(end[i]) - bit.sum(begin[i]);ans += cnt;bit.add(begin[i], 1);}return ans;}struct FenwickTree(T) {private {int _size;T[] _data;}this(int N) {_size = N;_data = new T[](_size + 1);}void add(int i, T x) {i++;while (i <= _size) {_data[i] += x;i += i & (-i);}}T sum(int r) {T res = 0;while (r > 0) {res += _data[r];r -= r & (-r);}return res;}}void scan(T...)(ref T args) {import std.stdio : readln;import std.algorithm : splitter;import std.conv : to;import std.range.primitives;auto line = readln().splitter();foreach (ref arg; args) {arg = line.front.to!(typeof(arg));line.popFront();}assert(line.empty);}void fillAll(R, T)(ref R arr, T value) {static if (is(typeof(arr[] = value))) {arr[] = value;}else {foreach (ref e; arr) {fillAll(e, value);}}}