結果
問題 | No.8113 How Many Liars Are There? |
ユーザー | 👑 獅子座じゃない人 |
提出日時 | 2024-03-29 16:03:23 |
言語 | C++17(gcc12) (gcc 12.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 71 ms / 2,000 ms |
コード長 | 3,777 bytes |
コンパイル時間 | 4,257 ms |
コンパイル使用メモリ | 278,192 KB |
実行使用メモリ | 19,456 KB |
最終ジャッジ日時 | 2024-09-30 21:55:08 |
合計ジャッジ時間 | 6,459 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
01_ | AC * 4 |
other | AC * 60 |
ソースコード
#include <bits/stdc++.h>#include <atcoder/all>using namespace std;using namespace atcoder;void or_assign(bool & l, bool r){l=l|r;}void or_assign(vector<bool>::reference l, bool r){l=l|r;}int main(void){int n;cin >> n;int k;cin >> k;vector<int> p(n);vector<int> indeg(n, 0);dsu uf(n);vector<bool> is_root(n, false);vector<bool> is_root_next(n, false);for(int v=0;v<n;++v){cin >> p[v];--p[v];if(uf.same(v, p[v])){is_root[v]=true;is_root_next[p[v]]=true;} else {++indeg[p[v]];}uf.merge(v, p[v]);}vector<int> a(n);for(int v=0;v<n;++v){cin >> a[v];}vector ans=vector(2*n+1, false);vector dp(n, vector(2*n+1, array<array<array<bool,2>,2>,2>()));vector<int> size(n, 1);int ans_size=0;vector groups=uf.groups();ans[0]=true;for(vector<int> & group: groups){queue<int> queue;for(int v: group){if(indeg[v]==0){queue.emplace(v);}for(int c_v=0;c_v<2;++c_v){for(int c_p=0;c_p<2;++c_p){for(int c_s=0;c_s<2;++c_s){or_assign(dp[v][c_v+(a[v]+c_v+c_p)%2][c_v][c_p][c_s], true);}}}}while(!queue.empty()){int v=queue.front();queue.pop();if(is_root[v]){vector dp_p=vector(2*(size[v]+ans_size)+1, false);for(int i=0;i<=2*size[v];++i){for(int c_v=0;c_v<2;++c_v){for(int c_p=0;c_p<2;++c_p){for(int j=0;j<=2*ans_size;++j){or_assign(dp_p[i+j], dp[v][i][c_v][c_p][c_p]&&ans[j]);}}}}ans_size+=size[v];for(int i=0;i<=2*ans_size;++i){ans[i]=dp_p[i];}} else {vector dp_p=vector(2*(size[v]+size[p[v]])+1, array<array<array<bool,2>,2>,2>());for(int i=0;i<=2*size[v];++i){for(int c_v=0;c_v<2;++c_v){for(int c_p=0;c_p<2;++c_p){for(int c_pp=0;c_pp<2;++c_pp){for(int j=0;j<=2*size[p[v]];++j){if(is_root_next[v]){or_assign(dp_p[i+j][c_p][c_pp][c_v], dp[v][i][c_v][c_p][c_v]&&dp[p[v]][j][c_p][c_pp][c_v]);} else {for(int c_s=0;c_s<2;++c_s){or_assign(dp_p[i+j][c_p][c_pp][c_s], dp[v][i][c_v][c_p][c_s]&&dp[p[v]][j][c_p][c_pp][c_s]);}}}}}}}size[p[v]]+=size[v];for(int i=0;i<=2*size[p[v]];++i){for(int c_v=0;c_v<2;++c_v){for(int c_p=0;c_p<2;++c_p){for(int c_s=0;c_s<2;++c_s){dp[p[v]][i][c_v][c_p][c_s]=dp_p[i][c_v][c_p][c_s];}}}}indeg[p[v]]-=1;if(indeg[p[v]]==0){queue.emplace(p[v]);}}}}cout << (ans[k] ? "Yes" : "No") << endl;return 0;}