제출 #1282760

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1282760		stefanneagu	Hiperkocka (COCI21_hiperkocka)	C++20	110 / 110	297 ms	28360 KiB

Main

#include <bits/stdc++.h>

using namespace std;

const int nmax = (1 << 16) + 1;

vector<pair<int, int>> adj[nmax];
int timer = 0;
int to[nmax];

void dfs_init(int i, int tata = -1) {
    for (auto &[it, c] : adj[i]) {
        if (it == tata) {
            continue;
        }
        c = timer++;
        dfs_init(it, i);
    }
}

bool kil = 0;
set<pair<int, int>> viz;
set<pair<int, int>> aux;

void dfs(int i, int val, int tata = -1) {
    for (auto &[it, c] : adj[i]) {
        if (it == tata) {
            continue;
        }
        int v1 = val, v2 = val ^ (1 << c);
        if (viz.find({min(v1, v2), max(v1, v2)}) != viz.end()) {
            kil = 1;
        }
        aux.insert({min(v1, v2), max(v1, v2)});
        to[it] = val ^ (1 << c);
        dfs(it, (val ^ (1 << c)), i);
    }
}

int32_t main() {
    ios_base::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int n;
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int a, b;
        cin >> a >> b;
        adj[a].push_back({b, 0});
        adj[b].push_back({a, 0});
    }
    dfs_init(0);
    cout << (1 << (n - 1)) << '\n';
    for (int i = 0; i < (1 << n); i++) {
        kil = 0;
        aux.clear();
        to[0] = i;
        dfs(0, i);
        if (kil) {
            continue;
        }
        for (auto it : aux) {
            viz.insert(it);
        }
        for (int j = 0; j <= n; j++) {
            cout << to[j] << " ";
        }
        cout << '\n';
    }
    return 0;
}

• Subtask 1: 110 / 110