結果

問題 No.2911 位相の公理
ユーザー detteiuu
提出日時 2024-10-04 22:43:54
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 599 ms / 2,000 ms
コード長 1,531 bytes
コンパイル時間 6,156 ms
コンパイル使用メモリ 316,244 KB
実行使用メモリ 5,248 KB
最終ジャッジ日時 2024-10-04 22:44:03
合計ジャッジ時間 7,432 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 24
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
#include <atcoder/all>
#define pass (void)0
#define INF (1<<30)-1
#define INFLL (1LL<<60)-1
using namespace std;
using namespace atcoder;
using mint = modint998244353;
using ll = long long;

int main() {
    int N, M;
    cin >> N >> M;
    vector<string> S(M);
    
    for (int i = 0; i < M; i++) {
        cin >> S[i];
    }

    vector<int> binS(M);
    for (int i = 0; i < M; i++) {
        int num = 0;
        for (int j = 0; j < N; j++) {
            if (S[i][j] == '1') {
                num |= 1 << j;
            }
        }
        binS[i] = num;
    }

    unordered_set<int> SET(binS.begin(), binS.end());
    if (SET.find((1 << N) - 1) == SET.end() || SET.find(0) == SET.end()) {
        cout << "No" << endl;
        return 0;
    }

    for (int i = 0; i < M - 1; i++) {
        for (int j = i + 1; j < M; j++) {
            if (SET.find(binS[i] & binS[j]) == SET.end()) {
                cout << "No" << endl;
                return 0;
            }
        }
    }

    vector<bool> now(1 << N, false);
    now[0] = true;

    for (int i = 0; i < M; i++) {
        vector<bool> nex(1<<N, false);
        for (int j = 0; j < (1 << N); j++) {
            if (!now[j]) continue;
            nex[j] = now[j];
            nex[j | binS[i]] = now[j];
        }
        now = nex;
    }

    for (int i = 0; i < (1 << N); i++) {
        if (now[i] && SET.find(i) == SET.end()) {
            cout << "No" << endl;
            return 0;
        }
    }

    cout << "Yes" << endl;
    return 0;
}
0