結果

問題 No.8122 How Many Liars Are There?
ユーザー 👑 獅子座じゃない人
提出日時 2025-01-15 19:34:03
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 77 ms / 2,000 ms
コード長 3,781 bytes
コンパイル時間 5,991 ms
コンパイル使用メモリ 335,344 KB
実行使用メモリ 19,456 KB
最終ジャッジ日時 2025-02-28 12:06:53
合計ジャッジ時間 10,723 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 65
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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[2*n-k] ? "Yes" : "No") << endl;
    return 0;
}
0