Submission #1114558

#	Time	Username	Problem	Language	Result	Execution time	Memory
1114558		vjudge1	Newspapers (CEOI21_newspapers)	C++17	12 / 100	222 ms	524288 KiB

newspapers

#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG 
    #include "/home/ahmetalp/Desktop/Workplace/debug.h"
#else
    #define debug(...) void(23)
#endif

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

    int N, M;
    std::cin >> N >> M;

    std::vector<std::vector<int>> gr(1 << N);
    for (int i = 0; i < M; ++i) {
        int A, B;
        std::cin >> A >> B;
        --A, --B;
        gr[A].emplace_back(B);
        gr[B].emplace_back(A);
    }

    std::vector<std::vector<std::pair<int, int>>> adj(1 << N);

    std::vector<int> dp(1 << N, -1), vis(1 << N);
    std::vector<std::pair<int, int>> save(1 << N);
    dp[0] = 0;
    auto dfs = [&](auto&& self, int mask) -> void {
        if (vis[mask]) {
            return;
        }
        vis[mask] = true;
        for (int i = 0; i < N; ++i) {
            int nmask = 0;
            for (int j = 0; j < N; ++j) {
                if (mask >> j & 1 && i != j) {
                    for (auto u : gr[j]) {
                        nmask |= (1 << u);
                    }
                }
            }
            debug(mask, nmask);
            adj[nmask].emplace_back(mask, i);
            self(self, nmask);
        }
    };
    dfs(dfs, (1 << N) - 1);

    std::vector<int> dep((1 << N), -1);
    std::vector<std::pair<int, int>> bef((1 << N));
    std::queue<int> que;
    que.emplace(0);
    dep[0] = 0;
    while (!que.empty()) {
        int v = que.front();
        que.pop();
        for (auto[u, i] : adj[v]) {
            if (dep[u] == -1) {
                dep[u] = dep[v] + 1;
                bef[u] = {v, i};
                que.emplace(u);
            }
        }
    }

    int ans = dep[(1 << N) - 1];

    if (ans == -1) {
        std::cout << "NO\n";
    } else {
        std::cout << "YES\n";
        std::cout << ans << '\n';
        int mask = (1 << N) - 1;
        while (mask != 0) {
            std::cerr << std::bitset<10>(mask) << '\n';
            std::cout << bef[mask].second + 1 << ' ';
            mask = bef[mask].first;
        }
        std::cout << '\n';
    }

    return 0;
}

• Subtask 1: 12 / 12
• Subtask 2: 0 / 8
• Subtask 3: 0 / 80