Submission #1257643

#	Time	Username	Problem	Language	Result	Execution time	Memory
1257643		makrav	City (JOI17_city)	C++20	100 / 100	332 ms	20924 KiB

Encoder

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

using namespace std;
using ll = long long;

#define pb push_back
#define all(x) (x).begin(), (x).end()
#define sz(x) (int) (x).size()

void Encode(int N, int A[], int B[])
{
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; i++) {
		g[A[i]].pb(B[i]);
		g[B[i]].pb(A[i]);
	}
	vector<int> rnd_ups(1 << 8);
	rnd_ups[0] = 1;
	for (int i = 1; i < 1 << 8; i++) {
		rnd_ups[i] = max(rnd_ups[i - 1] + 1, int(rnd_ups[i - 1] * 1.05));
	}
	vector<int> tin(N), X(N);
	int T = 0;
	auto dfs = [&](int v, int p, auto&&self) -> void {
		tin[v] = T++;
		for (int u : g[v]) {
			if (u != p) {
				self(u, v, self);
			}
		}
		int L = -1, R = sz(rnd_ups);
		while (R - L > 1) {
			int M = (L + R) / 2;
			if (rnd_ups[M] < T - tin[v]) L = M;
			else R = M;
		}
		T = tin[v] + rnd_ups[R];
		X[v] = R;
	};
	dfs(0, 0, dfs);
	for (int i = 0; i < N; i++) Code(i, (tin[i] << 8) | X[i]);
}		

Device

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

using namespace std;
using ll = long long;

vector<int> rnd_ups(1 << 8);

void InitDevice() {
	rnd_ups[0] = 1;
	for (int i = 1; i < 1 << 8; i++) {
		rnd_ups[i] = max(rnd_ups[i - 1] + 1, int(rnd_ups[i - 1] * 1.05));
	}
}

int Answer(long long S, long long T) {
	if (S == T) return 2;
	ll tin1 = S / (1 << 8), tin2 = T / (1 << 8), tout1 = tin1 + rnd_ups[S % (1 << 8)], tout2 = tin2 + rnd_ups[T % (1 << 8)];
	if (tin1 <= tin2 && tout2 <= tout1) return 1;
	if (tin2 <= tin1 && tout1 <= tout2) return 0;
	return 2;
	// if ((S&T) != std::min(S, T)) return 2;
	// if (H1 < H2) return 1;
	// return 0;
}

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