oj.uz

Submission #874851

# Submission time Handle Problem Language Result Execution time Memory
874851 2023-11-18T01:01:03 Z tsumondai Hiperkocka (COCI21_hiperkocka) C++14
110 / 110
 45 ms 36580 KB 
#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.0 / 110.0

# Verdict Execution time Memory Grader output
1 Correct 5 ms 23900 KB Output is correct
2 Correct 5 ms 23900 KB Output is correct
3 Correct 5 ms 23932 KB Output is correct
4 Correct 5 ms 23900 KB Output is correct
5 Correct 6 ms 23944 KB Output is correct
6 Correct 5 ms 23900 KB Output is correct
7 Correct 7 ms 23944 KB Output is correct
8 Correct 6 ms 23900 KB Output is correct
9 Correct 41 ms 36196 KB Output is correct
10 Correct 9 ms 25180 KB Output is correct
11 Correct 13 ms 26596 KB Output is correct
12 Correct 41 ms 36364 KB Output is correct
13 Correct 6 ms 24152 KB Output is correct
14 Correct 40 ms 36372 KB Output is correct
15 Correct 23 ms 29844 KB Output is correct
16 Correct 15 ms 26508 KB Output is correct
17 Correct 40 ms 36108 KB Output is correct
18 Correct 40 ms 36364 KB Output is correct
19 Correct 45 ms 36580 KB Output is correct
20 Correct 41 ms 36364 KB Output is correct
21 Correct 6 ms 23900 KB Output is correct
22 Correct 42 ms 36360 KB Output is correct
23 Correct 41 ms 36364 KB Output is correct
24 Correct 41 ms 36360 KB Output is correct
25 Correct 41 ms 36140 KB Output is correct
26 Correct 22 ms 29584 KB Output is correct