Submission #50014682

---

Source Code Expand

#include <bits/stdc++.h>

typedef long long valueType;
typedef std::vector<valueType> ValueVector;
typedef std::vector<ValueVector> ValueMatrix;
typedef std::vector<ValueMatrix> ValueCube;
typedef std::string string;
typedef std::vector<string> StringVector;
typedef std::vector<bool> bitset;
typedef std::vector<bitset> BitMatrix;
typedef std::pair<valueType, valueType> ValuePair;
typedef std::vector<ValuePair> PairVector;
typedef std::vector<PairVector> PairMatrix;
typedef std::tuple<valueType, valueType, valueType> ValueTuple;
typedef std::vector<ValueTuple> TupleVector;
typedef std::vector<TupleVector> TupleMatrix;
typedef std::set<valueType> ValueSet;

int main() {
    std::ios::sync_with_stdio(false);
    std::cin.tie(nullptr);
    std::cout.tie(nullptr);

    valueType P, B, N, M;

    std::cin >> P >> B >> N >> M;

    if (P > N + 1) {
        std::cout << "Yes" << std::endl;

        return 0;
    }

    PairVector edges(M);

    for (auto &[u, v] : edges) {
        std::cin >> u >> v;

        --u;
    }

    valueType const S = 1 << (N + 1);

    bitset ok(S, true);

    for (valueType s = 0; s < S; ++s) {
        bitset inSet(N + 1, false);

        for (valueType i = 0; i <= N; ++i)
            if ((s >> i) & 1)
                inSet[i] = true;

        for (auto const &[u, v] : edges) {
            if (inSet[u] && inSet[v])
                ok[s] = false;
        }
    }

    ValueVector F(S, std::numeric_limits<valueType>::max() >> 10);

    F[0] = 0;

    for (valueType s = 0; s < S; ++s) {
        for (valueType t = s; t > 0; t = (t - 1) & s)
            if (ok[t])
                F[s] = std::min(F[s], F[s ^ t] + 1);
    }

    if (F[S - 1] <= P) {
        std::cout << "Yes" << std::endl;
    } else {
        std::cout << "No" << std::endl;
    }

    return 0;
}

Submission Info

Judge Result