Submission #522233

#	Time	Username	Problem	Language	Result	Execution time	Memory
522233		blue	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	73 ms	11664 KiB

Main

#include <iostream>
#include <vector>
#include <algorithm>
#include <stack>
#include <queue>
#include <set>
#include <map>
#include <deque>
#include <string>
using namespace std;

using vi = vector<int>;
using vvi = vector<vi>;
using ll = long long;
using vll = vector<ll>;
using vvll = vector<vll>;

const int max_n = 16;

vi edge[1+max_n];

vi parent(1+max_n);
vi fake(1+max_n);
vi actual(1+max_n);
int node_ct = -1;

void dfs(int u, int p)
{
    node_ct++;
    parent[u] = p;
    fake[u] = node_ct;
    actual[node_ct] = u;

    for(int v: edge[u])
    {
        if(p == v) continue;
        dfs(v, u);
    }
}

int main()
{
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    int n;
    cin >> n;

    for(int e = 1; e <= n; e++)
    {
        int x, y;
        cin >> x >> y;
        edge[x].push_back(y);
        edge[y].push_back(x);
    }

    dfs(0, 0);

    // for(int i = 0; i <= n; i++) cerr << parent[i] << ' ';
    // cerr << '\n';


    //base case: 1 dimension
    vvi a(1, vi{0, 1});

    for(int d = 2; d <= n; d++)
    {
        vvi b1 = a;
        vvi b2 = a;
        for(int i = 0; i < (1 << (d-2)); i++)
        {
            for(int j = 0; j <= d-1; j++)
            {
                b2[i][j] = b2[i][j] ^ (1 << (d-1)) ^ (1 << (d-2));
            }

            a.push_back(b2[i]);
        }

        // cerr << fake[parent[actual[d]]] << '\n';

        // cerr << "preliminary: \n";
        // for(auto f: a)
        // {
        //     for(int g: f) cerr << g << ' ';
        //     cerr << '\n';
        // }
        // cerr << '\n';

        // a.clear();

        // a.push_back(b1[i]);
        for(int i = 0; i < (1 << (d-1)); i++)
        {
            a[i].push_back(a[i][ fake[ parent[ actual[d] ] ] ] ^ (1 << (d-1)));
            // cerr << "pushing back " << (a[i][fake[parent[actual[d]]]] ^ (1 << (d-1))) << '\n';
        }

        // cerr << "post: \n";
        // for(auto f: a)
        // {
        //     for(int g: f) cerr << g << ' ';
        //     cerr << '\n';
        // }
        // cerr << '\n';
    }
    // cerr << "\n\n\n\n";

    // for(int i = 0; i <= n; i++) cerr << parent[i] << ' ' << fake[i] << ' ' << actual[i] <<  '\n';



    // cerr << "\n\n\n\n";






    cout << (1 << (n-1)) << '\n';
    for(int k = 0; k < (1 << (n-1)); k++)
    {
        for(int i = 0; i <= n; i++)
        {
            // cout << a[k][i] << "/" << actual[a[k][i]] << ' ';
            cout << a[k][fake[i]] << ' ';
        }
        cout << '\n';
    }
}

• Subtask 1: 110 / 110