【競プロ】1日1AC : ABC147 C問題 HonestOrUnkind2

今日の問題はこちら。

やりたいことをしっかり整理して処理すれば解けるはずです。

提出コードと考え方

まず、誰が「正直者」で誰が「不親切な人」なのかを決めます。\(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;
}