結果

問題 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
権限があれば一括ダウンロードができます

ソースコード

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[k] ? "Yes" : "No") << endl;
return 0;
}
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0