Submission #1291120

#	Time	Username	Problem	Language	Result	Execution time	Memory
1291120		MisterReaper	City (JOI17_city)	C++20	22 / 100	222 ms	24780 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]);
	}

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

	std::vector<i64> codes(N);
	for (int v = 0; v < N; ++v) {
		codes[v] = tin[v] * 250000LL + tout[v];
	}

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

Device

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

using i64 = long long;

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

void InitDevice() {
}

int Answer(long long S, long long T) {
	i64 tinS = S / 250000;
	i64 toutS = S % 250000;
	i64 tinT = T / 250000;
	i64 toutT = T % 250000;
	if (tinT <= tinS && tinS <= toutT) {
		return 0;
	}
	if (tinS <= tinT && tinT <= toutS) {
		return 1;
	}
	return 2;
}

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