Submission #1143070

#	Time	Username	Problem	Language	Result	Execution time	Memory
1143070		CDuong	City (JOI17_city)	C++20	8 / 100	257 ms	22972 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

void Encode(int N, int A[], int B[]) {
	vector<vector<int>> g(N);
	for (int i = 0; i < N - 1; ++i) {
		int u = A[i], v = B[i];
		g[u].emplace_back(v);
		g[v].emplace_back(u);
	}

	vector<int> a(1 << 9);
	for (int i = 0; i + 1 < 1 << 9; ++i) {
		a[i + 1] = max(a[i] + 1.0L, a[i] * 1.05L);
	}

	int tdfs = 0;
	vector<i64> tin(N), tout(N);
	auto dfs = [&](auto self, int u, int p) -> void {
		tin[u] = tdfs++;
		for (auto v : g[u]) if (v != p) {
			self(self, v, u);
		}
		int len = tdfs - tin[u] - 1;
		len = *lower_bound(all(a), len);
		tdfs = tin[u] + len + 1;
		tout[u] = tdfs;
	};
	dfs(dfs, 0, -1);

	for (int u = 0; u < N; ++u) {
		assert(tin[u] < 1 << 19);
		int len = tout[u] - tin[u] - 1;
		Code(u, tin[u] << 9 | (lower_bound(all(a), len) - a.begin()));
	}
}

Device

#include "Device.h"
#include <bits/stdc++.h>
#define taskname ""
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
#define i64 long long
#define isz(x) (int)x.size()
using namespace std;

vector<int> a;

void InitDevice() {
	a.resize(1 << 9);
	for (int i = 0; i + 1 < 1 << 9; ++i) {
		a[i + 1] = max(a[i] + 1.0L, a[i] * 1.05L);
	}
}

const int lim = (1 << 9) - 1;

int Answer(i64 S, i64 T) {
	int Sl = S >> 9, Sr = Sl + a[S & lim] + 1;
	int Tl = T >> 9, Tr = Tl + a[T & lim] + 1;
	if (Tl <= Sl and Sr <= Tr) return 0;
	if (Sl <= Tl and Tr <= Sr) return 1;
	return 2;
}

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