Submission #496635

#	Time	Username	Problem	Language	Result	Execution time	Memory
496635		JovanB	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	56 ms	5964 KiB

Main

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

const int N = 17;

int gde[(1<<N)][N+1];

vector <int> ord, parent;
vector <int> graf[N+1];

void dfs(int v, int p){
    ord.push_back(v);
    parent.push_back(p);
    for(auto c : graf[v]){
        if(c != p) dfs(c, v);
    }
}

bool taken[(1<<N)];

vector <int> vc;

void dupliraj(int n, int v, int p){
    vc.push_back(v);
    for(int i=0; i<n; i++){
        gde[i][v] = gde[i][p] + 2*n;
        taken[gde[i][v]] = 1;
    }
    int k = 2*n;
    for(int i=0; i<n; i++){
        while(taken[k]) k++;
        int xr = k^gde[i][p];
        for(int j=0; j<vc.size(); j++){
            gde[i + n][vc[j]] = gde[i][vc[j]] ^ xr;
        }
        taken[k] = 1;
    }
}

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    int n;
    cin >> n;
    for(int i=1; i<=n; i++){
        int a, b;
        cin >> a >> b;
        graf[a].push_back(b);
        graf[b].push_back(a);
    }
    dfs(0, -1);
    reverse(ord.begin(), ord.end());
    reverse(parent.begin(), parent.end());
    ord.pop_back();
    parent.pop_back();
    gde[0][0] = 0;
    gde[0][ord.back()] = 1;
    vc.push_back(0);
    vc.push_back(ord.back());
    ord.pop_back();
    parent.pop_back();
    int tren = 1;
    while(ord.size()){
        dupliraj(tren, ord.back(), parent.back());
        tren *= 2;
        ord.pop_back();
        parent.pop_back();
    }
    cout << (1<<(n-1)) << "\n";
    for(int i=0; i<(1<<(n-1)); i++){
        for(int j=0; j<=n; j++){
            cout << gde[i][j] << " ";
        }
        cout << "\n";
    }
    return 0;
}

Compilation message (stderr)

Main.cpp: In function 'void dupliraj(int, int, int)':
Main.cpp:36:23: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   36 |         for(int j=0; j<vc.size(); j++){
      |                      ~^~~~~~~~~~

• Subtask 1: 110 / 110