結果
問題 | No.778 クリスマスツリー |
ユーザー |
![]() |
提出日時 | 2020-08-20 14:35:49 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
CE
(最新)
AC
(最初)
|
実行時間 | - |
コード長 | 1,485 bytes |
コンパイル時間 | 30,435 ms |
コンパイル使用メモリ | 5,504 KB |
最終ジャッジ日時 | 2025-01-13 04:23:21 |
ジャッジサーバーID (参考情報) |
judge1 / judge3 |
(要ログイン)
コンパイルエラー時のメッセージ・ソースコードは、提出者また管理者しか表示できないようにしております。(リジャッジ後のコンパイルエラーは公開されます)
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
ただし、clay言語の場合は開発者のデバッグのため、公開されます。
コンパイルメッセージ
コンパイルが30秒の制限時間を超えました
ソースコード
//https://yukicoder.me/problems/no/778#include <iostream>#include <string>#include <vector>#include <deque>#include <queue>#include <algorithm>#include <bitset>#include <tuple>#include <set>#include <map>#define range(i, r) for(int i=0;i<r;i++)#define ranges(i, l, r) for(int i=l;i<r;i++)#define vv(a, b, c, d) vector<vector<d> >(a, vector<d>(b, c))#define vvi std::vector<std::vector<int> >#define vvl std::vector<std::vector<ll> >#define MODs 1000000007;#define MODn 1000000009;typedef long long int ll;using namespace std;ll ans=0;int M=1;vvi num = vv(300000,0,0,int);std::vector<int> bit;void init(int N){while(M<N) M*=2;M= M*2-1;for(int i=0;i<M;i++) bit.push_back(0);}void add(int a, int k){k += (M+1)/2-1;bit[k]+=a;while(k>0){k=(k-1)/2;bit[k]=bit[k*2+1]+bit[k*2+2];}}int query(int a, int b, int l, int r, int k){if(r<=a||b<=l) return 0;if(a<=l && r<=b) return bit[k];int A = query(a, b, l, (l+r)/2, k*2+1);int B = query(a, b, (l+r)/2, r, k*2+2);return A+B;}void dfs(int cu, int pa=-1){//std::cout << cu << '\n';ans += query(0, cu+1, 0, (M+1)/2, 0);add(1, cu);for(int i=0;i<num[cu].size();i++) if(num[cu][i]!=pa) dfs(num[cu][i], cu);add(-1, cu);}int main(int argc, char const *argv[]) {int N;std::cin >> N;init(N);for(int i=1;i<N;i++){int a;std::cin >> a;num[i].push_back(a);num[a].push_back(i);}dfs(0);std::cout << ans << '\n';return 0;}