Submission #658872

#	Time	Username	Problem	Language	Result	Execution time	Memory
658872		Foxyy	Hiperkocka (COCI21_hiperkocka)	C++17	110 / 110	51 ms	3660 KiB

Main

#include <bits/stdc++.h>
using namespace std;
 
#define ll long long
#define Foxyy cin.tie(0); cout.sync_with_stdio(0); cout.tie(0);
 
struct Solver {
	int& n;
	vector<vector<int>>& adj;
	
	void solve() {
		if (n == 1) {
			cout << "1\n";
			cout << "0 1\n";
			return;
		}
		vector<int> tree(n+1);
		tree[0] = 0;
		queue<pair<int, int>> q;
		for (int i : adj[0]) {
			q.push({i, 0});
		}
		int cnt = 0;
		while (not q.empty()) {
			auto [u, p] = q.front();
			q.pop();
			tree[u] = tree[p] ^ (1 << cnt);
//			cerr << u << ' ' << p << ' ' << tree[u] << ' ' << tree[p] << '\n';
			cnt++;
			for (int v : adj[u]) if (v != p) {
				q.push({v, u});
			}
		}
		
		vector<int> masks(n-1);
		for (int i = 0; i < n-1; i++) {
			masks[i] = (3 << i);
		}
		
		cout << (1 << (n-1)) << '\n';
		for (int i = 0; i < (1 << (n-1)); i++) {
			int mask = 0;
			for (int j = 0; j < n-1; j++) {
				if ((i >> j) & 1) {
					mask ^= masks[j];
				}
			}
			for (auto x : tree) {
				cout << (x ^ mask) << ' ';
			}
			cout << '\n';
		}
	}
};
 
signed main() {
	Foxyy
	
	int T = 1;
//	cin >> T;
	while(T--) {
		int n;
		cin >> n;
		vector<vector<int>> adj(n+1);
		for (int i = 0; i < n; i++) {
			int a, b;
			cin >> a >> b;
			adj[a].push_back(b);
			adj[b].push_back(a);
		}
		
		Solver solver{n, adj};
		solver.solve();
	}
}

• Subtask 1: 110 / 110