Submission #851889

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
851889	2023-09-20T18:39:59 Z	vjudge1	Hiperkocka (COCI21_hiperkocka)	C++17	0 / 110	1 ms	344 KB

Main

//author:
#include <bits/stdc++.h>
using namespace std;
using i64 = long long;

#define ONLINE_JUDGE

struct DSU {
    vector <int> par;
    DSU(int n) {
        par.resize(n);
        iota(par.begin(), par.end(), 0ll);
    }

    bool same(int a, int b) {
        return get(a) == get(b);
    }

    inline int get(int a) {
        return par[a] = (par[a] == a ? a : get(par[a]));
    }

    void unite(int u, int v) {
        u = get(u);
        v = get(v);

        par[u] = v;
    }
};

bool check(int a) {
    int cnt = 0;
    while(a) {
        if(a & 1)
            cnt++;

        a >>= 1;
    }

    return cnt == 1;
}

void solve() {
    int n;
    cin >> n;

    DSU dsu(1 << n);
    for(int i = 1; i <= n; i++) {
        int u, v;
        cin >> u >> v;

        if(!check(u ^ v)) {
            dsu.unite(u, v);
        }
    }

    vector <bool> ok(1 << n);
    auto check = [&](int x) -> bool {
        vector <int> vec;
        vec.emplace_back(x);
        for(int i = 0; i <= n -1; i++)
            vec.emplace_back(x ^ (1 << i));

        for(int &i : vec)
            if(ok[i])
                return false;

        for(int &i : vec)
            ok[i] = true;

        for(int &i : vec)   
            for(int &j : vec)
                if(i != j && dsu.same(i, j))
                    return false;

        return true;
    };

    vector <vector <int>> ans;
    for(int i = 0; i < (1 << n); i++) {
        if(check(i)) {
            ans.emplace_back();
            ans.back().emplace_back(i);
            for(int j = 0; j <= n -1; j++) {
                ans.back().emplace_back(i ^ (1 << j));
            }
        }
    }

    cout << (int) ans.size() << "\n";
    for(auto &vec : ans) {
        for(auto &i : vec)
            cout << i << " ";
        cout << "\n";
    }
    
    return;
}

signed main() {
    #ifndef ONLINE_JUDGE
        freopen(".in", "r", stdin);
        freopen(".out", "w", stdout);
    #endif

    ios_base::sync_with_stdio(false);
    cin.tie(NULL); cout.tie(NULL);

    int t = 1; //cin >> t;
    while(t--)
        solve();

    return 0;
}

Subtask #1

0.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Incorrect	1 ms	344 KB	Output isn't correct
2	Halted	0 ms	0 KB	-