Submission #862648

#	Submission time	Handle	Problem	Language	Result	Execution time	Memory
862648	2023-10-18T17:22:39 Z	AbdelmagedNour	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	206 ms	28736 KB

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.0 / 110.0

#	Verdict	Execution time	Memory	Grader output
1	Correct	0 ms	348 KB	Output is correct
2	Correct	0 ms	456 KB	Output is correct
3	Correct	1 ms	348 KB	Output is correct
4	Correct	0 ms	348 KB	Output is correct
5	Correct	0 ms	348 KB	Output is correct
6	Correct	1 ms	348 KB	Output is correct
7	Correct	1 ms	348 KB	Output is correct
8	Correct	2 ms	604 KB	Output is correct
9	Correct	206 ms	28256 KB	Output is correct
10	Correct	22 ms	3420 KB	Output is correct
11	Correct	35 ms	6456 KB	Output is correct
12	Correct	190 ms	28496 KB	Output is correct
13	Correct	3 ms	860 KB	Output is correct
14	Correct	200 ms	28476 KB	Output is correct
15	Correct	77 ms	13440 KB	Output is correct
16	Correct	39 ms	6376 KB	Output is correct
17	Correct	187 ms	28488 KB	Output is correct
18	Correct	200 ms	28736 KB	Output is correct
19	Correct	158 ms	28500 KB	Output is correct
20	Correct	182 ms	28496 KB	Output is correct
21	Correct	2 ms	604 KB	Output is correct
22	Correct	193 ms	28344 KB	Output is correct
23	Correct	192 ms	28276 KB	Output is correct
24	Correct	196 ms	28396 KB	Output is correct
25	Correct	196 ms	28420 KB	Output is correct
26	Correct	79 ms	13392 KB	Output is correct