Submission #1291113

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291113		MisterReaper	City (JOI17_city)	C++20	8 / 100	2 ms	352 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 d = 1; d < D; ++d) {
		int n = int(nodes[d].size());
		for (int x = 1; ; ++x) {
			bool good = false;
			for (int i = 1; i <= x; ++i) {
				__int128_t cnt = comb(x, i);
				if (cnt >= n) {
					debug(x, i);
					good = true;
					int j = 0;
					for (int m = 0; m < (1 << x); ++m) {
						if (__builtin_popcount(m) != i) {
							continue;
						}
						int v = nodes[d][j];
						codes[v] = codes[par[v]] | (m << used);
						j += 1;
						if (j == n) {
							break;
						}
					}
					break;
				}
			}
			if (good) {
				used += x;
				break;
			}
		}
	}

	for (int v = 0; v < N; ++v) {
		Code(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) {
	if (S > T && (S & T) == T) {
		return 0;
	}
	if (S < T && (S & T) == S) {
		return 1;
	}
	return 2;
}

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