Submission #862648

#	Time	Username	Problem	Language	Result	Execution time	Memory
862648		AbdelmagedNour	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	206 ms	28736 KiB

Main

#include <bits/stdc++.h>
#pragma GCC optimize("Ofast,unroll-loops")
using namespace std;
typedef long long ll;
const int N=17;
vector<vector<int>>adj(N);
int val[N],id=-1;
void dfs(int v,int p){
    id++;
    for(auto u:adj[v]){
        if(u==p)continue;
        val[u]=val[v]^(1<<id);
        dfs(u,v);
    }
}
vector<pair<int,int>>edges;
set<pair<int,int>>covered;
bool check(int mask){
    for(auto[u,v]:edges){
        int a=val[u]^mask,b=val[v]^mask;
        if(a>b)swap(a,b);
        if(covered.find({a,b})!=covered.end())return 0;
    }
    return 1;
}
void add(int mask){
    for(auto[u,v]:edges){
        int a=val[u]^mask,b=val[v]^mask;
        if(a>b)swap(a,b);
        covered.insert({a,b});
    }
}
int main(){
	ios_base::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
    int n;
    cin>>n;
	for(int i=0;i<n;i++){
		int u,v;
		cin>>u>>v;
		adj[u].push_back(v);
		adj[v].push_back(u);
        edges.push_back({u,v});
    }
    dfs(0,0);
    vector<int>res;
    for(int mask=0;mask<(1<<n);mask++){
        if(check(mask))res.push_back(mask),add(mask);
    }
    cout<<res.size()<<"\n";
    for(auto mask:res){
        for(int i=0;i<=n;i++)cout<<(val[i]^mask)<<" ";
        cout<<"\n";
    }
	return 0;
}

• Subtask 1: 110 / 110