結果
問題 |
No.1878 union-find の数え上げ
|
ユーザー |
![]() |
提出日時 | 2022-03-18 21:59:46 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 703 bytes |
コンパイル時間 | 3,391 ms |
コンパイル使用メモリ | 229,904 KB |
実行使用メモリ | 19,328 KB |
最終ジャッジ日時 | 2024-10-03 09:33:58 |
合計ジャッジ時間 | 4,240 ms |
ジャッジサーバーID (参考情報) |
judge5 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 8 |
ソースコード
#include <bits/stdc++.h> using namespace std; #include <atcoder/all> using namespace atcoder; using ll=long long; using Graph=vector<vector<int>>; #define MAX 1000 //#define MOD 1000000007 #define MOD 998244353 //#define INF 1000000000 #define INF 1000000000000000000 ll dfs(Graph &G,int v,int p,vector<ll> &multi){ ll ret=1; for(int nv:G[v]){ if(nv==p){ continue; } multi[v]*=dfs(G,nv,v,multi)+1; multi[v]%=MOD; ret*=multi[nv]; ret%=MOD; } return ret; } int main(){ int N; cin>>N; vector<int> p(N); Graph G(N); for(int i=1;i<N;i++){ cin>>p[i]; p[i]--; G[p[i]].push_back(i); } vector<ll> multi(N,1); cout<<dfs(G,0,-1,multi)<<'\n'; }