結果
問題 | No.1878 union-find の数え上げ |
ユーザー |
![]() |
提出日時 | 2023-04-12 17:56:32 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 1,194 bytes |
コンパイル時間 | 3,623 ms |
コンパイル使用メモリ | 255,996 KB |
最終ジャッジ日時 | 2025-02-12 05:17:20 |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 2 |
other | AC * 5 WA * 8 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;using ll=long long;using ld=long double;ld pie=3.141592653589793;ll inf=144494;ll mod=998244353;int main(){ll n;cin >> n;if (n==1){cout << 1 << endl;return 0;}vector<vector<ll>>g(n);for (ll i = 0; i < n-1; i++){ll a;cin >> a;a--;g[a].push_back(i+1);}vector<ll>memo(n,inf);memo[0]=0;queue<ll>que;que.push(0);while (!que.empty()){ll v=que.front();que.pop();for (ll i = 0; i < g[v].size(); i++){if (memo[g[v][i]]>memo[v]+1){memo[g[v][i]]=memo[v]+1;que.push(g[v][i]);}}}ll ans=1;for (ll i = 0; i < n; i++){bool ok=true;for (ll j = 0; j < g[i].size(); j++){if (memo[g[i][j]]>memo[i]){ok=false;break;}}if (ok){ans*=memo[i];ans%=mod;}}cout << ans << endl;}