今日の問題はこちら。
やりたいことをしっかり整理して処理すれば解けるはずです。
提出コードと考え方
まず、誰が「正直者」で誰が「不親切な人」なのかを決めます。\(N\) が小さいのでbit全探索ですべて調べることにしましょう。
次に、証言が矛盾するかを調べます。「不親切な人」の証言は考える必要がなく、「正直者」の証言だけを見れば良いです。
bit全探索が偉大なので実装はそこまで重くないです。人の番号を0-indexedに直して入力を受け取ると混乱せずに済みます。
#include <bits/stdc++.h>
using namespace std;
#define rep(i,n) for (int i = 0;i < n;i++)
int n;
vector<vector<pair<int,int>>> tes(15,vector<pair<int,int>>());
bool isConsistent(bitset<15> s){
rep(i,n){
if(!s.test(i)) continue;
for(auto p : tes[i]){
if(s.test(p.first) != p.second) return false;
}
}
return true;
}
int main() {
cin >> n;
rep(i,n){
int a;
cin >> a;
rep(j,a){
int x,y;
cin >> x >> y;
x--;
tes[i].push_back(make_pair(x,y));
}
}
int ans = 0;
for(int bit = 0;bit < (1< s(bit);
if(isConsistent(s)) ans = max(ans,(int)s.count());
}
cout << ans << endl;
}
コメント