Submission #1291117

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291117		MisterReaper	City (JOI17_city)	C++20	0 / 100	2 ms	340 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>

using i64 = long long;

#ifdef DEBUG
	#include "../debug.h"
#else
	#define debug(...) void(23)
#endif

__int128_t comb(int x, int y) {
	__int128_t res = 1;
	for (int i = y + 1; i <= x; ++i) {
		res *= i;
	}
	for (int i = 1; i <= x - y; ++i) {
		res /= i;
	}
	return res;
}

void Encode(int N, int A[], int B[]) {
	// for (int i = 0; i < N; ++i) {
	// 	Code(i, 0LL);
	// }
	std::vector<std::vector<int>> adj(N);
	for (int i = 0; i < N - 1; ++i) {
		adj[A[i]].emplace_back(B[i]);
		adj[B[i]].emplace_back(A[i]);
	}

	std::vector<int> dep(N), par(N);
	auto dfs = [&](auto&& self, int v) -> void {
		for (auto u : adj[v]) {
			if (u == par[v]) {
				continue;
			}
			par[u] = v;
			dep[u] = dep[v] + 1;
			self(self, u);
		}
	};
	dfs(dfs, 0);

	debug(dep);

	const int D = *std::max_element(dep.begin(), dep.end()) + 1;

	std::vector<std::vector<int>> nodes(D);
	for (int i = 0; i < N; ++i) {
		nodes[dep[i]].emplace_back(i);
	}

	int used = 0;
	std::vector<int> codes(N);
	for (int v = 0; v < N; ++v) {
		codes[v] |= dep[v];
	}
	used += 5;
	for (int d = 1; d < D; ++d) {
		int n = int(nodes[d].size());
		debug(n);
		for (int x = 1; ; ++x) {
			int cnt = (1 << x);
			if (n <= cnt) {
				int j = 0;
				for (int m = 0; m < (1 << x); ++m) {
					int v = nodes[d][j];
					codes[v] |= (codes[par[v]] & ~31) | (m << used);
					j += 1;
					if (j == n) {
						break;
					}
				}
				used += x;
				break;
			}
		}
	}

	for (int v = 0; v < N; ++v) {
		Code(v, codes[v]);
		debug(v, codes[v]);
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>

#ifdef DEBUG
	// #include "../debug.h"
#else
	#define debug(...) void(23)
#endif

void InitDevice() {
}

int Answer(long long S, long long T) {
	int depS = S & 31;
	int depT = T & 31;
	S >>= 5;
	T >>= 5;
	// std::cerr << "deps: " << depS << ' ' << depT << '\n';
	if (depS > depT && (S & T) == T) {
		return 0;
	}
	if (depS < depT && (S & T) == S) {
		return 1;
	}
	return 2;
}

• Subtask 1: 0 / 8
• Subtask 2: 0 / 92