Submission #874851

#	Time	Username	Problem	Language	Result	Execution time	Memory
874851		tsumondai	Hiperkocka (COCI21_hiperkocka)	C++14	110 / 110	45 ms	36580 KiB

Main

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

#define int long long
#define fi first
#define se second
#define pb push_back
#define mp make_pair
#define foru(i, l, r) for(int i = l; i <= r; i++)
#define ford(i, r, l) for(int i = r; i >= l; i--)
#define __TIME  (1.0 * clock() / CLOCKS_PER_SEC)

typedef pair<int, int> ii;
typedef pair<ii, int> iii;
typedef pair<ii, ii> iiii;
 
const int N = 1e6 + 5;
 
const int oo = 1e18, mod = 1e9 + 7;
 
int n, m, k;
string s;
vector<int> edges[N];

void process() {
	cin >> n;
	foru(i,1,n) {
		int u, v; cin >> u >> v;
		edges[u].pb(v);
		edges[v].pb(u);
	}
	vector<int> ord(n+5, -1), p(n+5);
	int t=0;
	queue<int> Q({0});
	ord[0]=t++;
	while (!Q.empty()) {
		int x=Q.front();
		Q.pop();
		for (int y: edges[x]) {
			if (ord[y]!=-1) continue;
			ord[y]=t++;
			p[ord[y]]=ord[x];
			Q.push(y);
		}
	}

	vector<vector<int>> sol= {{0,1}};
	foru(i,1,n-1) {
		int k=sol.size();
		foru(j,0,k-1) {
			sol.pb(sol[j]);
			for (auto &x: sol.back()) {
				x^=1^(1<<i);
			}
		}
		for (auto &v: sol) {
			v.pb(v[p[i+1]] ^ (1<<i));
		}
	}

	cout << sol.size() << '\n';
	for (auto &v: sol) {
		foru(i,0,n) {
			cout << v[ord[i]] << ' ';
		}
		cout << '\n';
	}
	
    return;
}

signed main() {
    cin.tie(0)->sync_with_stdio(false);
    //freopen(".inp", "r", stdin);
    //freopen(".out", "w", stdout);
    process();
    cerr << "Time elapsed: " << __TIME << " s.\n";
    return 0;
}

/*
Xét các trường hợp đặc biệt
Kiểm tra lại input/output
Cố gắng trâu
Lật ngược bài toán
Calm down and get VOI 
Flow:
trong một hình q(n) 
có 2^(n-1) bản sao của cây T với n node bao quanh
nói cách khác, hình q(n) là đồ thị gồm 2^n node
được đánh dấu từ 0 đến n-1
và node x và node y chỉ được kết nối nếu xor 
của chúng là số mũ 2
một cây được phép đặt vào nếu
node của cây đại diện cho một số node nào đó trong hcn
các nod phải khác nhau
nếu có cạnh giữua chúng thì phải có cạnh giữa các node
trong hyper
địt con mẹ adhoc
*/

• Subtask 1: 110 / 110