Submission #964608

#	Time	Username	Problem	Language	Result	Execution time	Memory
964608		Ghetto	Newspapers (CEOI21_newspapers)	C++17	0 / 100	52 ms	100788 KiB

newspapers

#include <bits/stdc++.h>
using namespace std;
const int MAX_N = 20 + 2;

int n, m;
vector<int> adj[MAX_N];

int seen[MAX_N];
void dfs1(int u, int par) {
    seen[u] = 1;
    for (int v : adj[u]) {
        if (v == par) continue;
        if (!seen[v]) dfs1(v, u);
        else if (seen[v] == 1) {
            cout << "NO" << '\n';
            exit(0);
        }
    }
    seen[u] = 2;
}
void cycle_check() {
    for (int i = 1; i <= n; i++) {
        if (seen[i] == 2) continue;
        dfs1(i, -1);
    }
    assert(m == n - 1);
}

vector<int> mask_adj[1 << MAX_N];
void precomp() {
    for (int mask = 0; mask < (1 << n); mask++) {
        for (int u = 1; u <= n; u++) {
            if (mask & (1 << (u - 1))) continue;
            int new_mask = (mask | (1 << (u - 1)));

            int adj_mask = 0;
            for (int v = 1; v <= n; v++) {
                bool on = true;
                for (int w : adj[v]) if (!(new_mask & (1 << (w - 1)))) on = false;
                if (on) adj_mask = (adj_mask | (1 << (v - 1)));
            }

            mask_adj[mask].push_back(adj_mask);
            // cout << mask << " " << adj_mask << endl;
        }
    }
}

bool mask_seen[1 << MAX_N];
void dfs2(int mask) {
    mask_seen[mask] = true;
    for (int adj_mask : mask_adj[mask]) {
        if (mask_seen[adj_mask]) continue;
        dfs2(adj_mask);
    }
}

int main() {
    // freopen("news.in", "r", stdin);

    cin >> n >> m;
    for (int i = 1; i <= m; i++) {
        int u, v; cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    cycle_check();
    precomp();
    dfs2(0);

    bool ans = mask_seen[(1 << n) - 1];
    cout << (ans ? "YES" : "NO") << '\n';
}

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