結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2018-12-28 09:24:52 |
言語 | C++11 (gcc 13.3.0) |
結果 |
AC
|
実行時間 | 102 ms / 2,000 ms |
コード長 | 1,571 bytes |
コンパイル時間 | 706 ms |
コンパイル使用メモリ | 87,544 KB |
実行使用メモリ | 17,732 KB |
最終ジャッジ日時 | 2024-10-14 01:53:57 |
合計ジャッジ時間 | 2,079 ms |
ジャッジサーバーID (参考情報) |
judge2 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 12 |
コンパイルメッセージ
main.cpp: In function ‘int main()’: main.cpp:76:8: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 76 | scanf("%d", &n); | ~~~~~^~~~~~~~~~ main.cpp:80:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result] 80 | scanf("%d", prts + i); | ~~~~~^~~~~~~~~~~~~~~~
ソースコード
/* -*- coding: utf-8 -*-** 778.cc: No.778 クリスマスツリー - yukicoder*/#include<cstdio>#include<cstdlib>#include<cstring>#include<cmath>#include<iostream>#include<string>#include<vector>#include<map>#include<set>#include<stack>#include<list>#include<queue>#include<deque>#include<algorithm>#include<numeric>#include<utility>#include<complex>#include<functional>using namespace std;/* constant */const int MAX_N = 200000;/* typedef */typedef long long ll;typedef vector<int> vi;template <typename T, const int MAX_N>struct BIT {int n;T bits[MAX_N + 1];BIT() {}void init(int _n) {n = _n;memset(bits, 0, sizeof(bits));}T sum(int x) {T s = 0;while (x > 0) {s += bits[x];x -= (x & -x);}return s;}void add(int x, T v) {while (x <= n) {bits[x] += v;x += (x & -x);}}};/* global variables */int prts[MAX_N], cis[MAX_N], avs[MAX_N];vi clds[MAX_N];BIT<int,MAX_N> bit;/* subroutines *//* main */int main() {int n;scanf("%d", &n);prts[0] = -1;for (int i = 1; i < n; i++) {scanf("%d", prts + i);clds[prts[i]].push_back(i);}memset(cis, -1, sizeof(cis));bit.init(n);ll sum = 0;for (int u = 0, rn = 0; u >= 0;) {if (cis[u] < 0)avs[u] = rn - bit.sum(u);if (++cis[u] >= clds[u].size()) {sum += (rn - bit.sum(u)) - avs[u];bit.add(u + 1, 1);rn++;u = prts[u];}elseu = clds[u][cis[u]];}printf("%lld\n", sum);return 0;}