Submission #1164267

#	Time	Username	Problem	Language	Result	Execution time	Memory
1164267		OI_Account	City (JOI17_city)	C++20	100 / 100	300 ms	29568 KiB

Encoder

#include "Encoder.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 250'000;
const int T1 = 19;
const int T2 = 9;

static int n, ans[N + 10], len[N + 10];
static int k, x[N + 10], sum[N + 10];
static vector<int> adj[N + 10];

static void calcX() {
	for (int i = 1; i <= 30; i++)
		x[i] = i;
	k = 30;
	while (x[k] < (1 << T1)) {
		x[k + 1] = (x[k] * 27) / 26;
		k++;
	}
}

static void dfsLen(int u = 1, int par = 0) {
	int t = 1;
	for (auto v: adj[u])
		if (v != par) {
			dfsLen(v, u);
			sum[v] += t;
			t += x[len[v]];
		}
	len[u] = lower_bound(x + 1, x + k + 1, t) - x;

}

static void dfsAns(int u = 1, int par = 0, int up = 0) {
	up += sum[u];
	ans[u] = up + 1;
	for (auto v: adj[u])
		if (v != par)
			dfsAns(v, u, up);
}

static void writeOutput() {
	for (int i = 1; i <= n; i++) {
		//cout << i - 1 << ": " << ans[i] << ' ' << ans[i] + x[len[i]] - 1 << endl;
		ans[i] = (ans[i] << T2) + len[i];
		Code(i - 1, ans[i]);
	}
}

void Encode(int N, int A[], int B[]) {
	n = N;
	for (int i = 0; i < n - 1; i++) {
		int u = A[i] + 1, v = B[i] + 1;
		adj[u].push_back(v);
		adj[v].push_back(u);
	}
	calcX();
	dfsLen();
	dfsAns();
	writeOutput();
}

Device

#include "Device.h"
#include <bits/stdc++.h>
using namespace std;

const int N = 250'000;
const int T1 = 19;
const int T2 = 9;

static int k, x[N + 10];

static void calcX() {
	for (int i = 1; i <= 30; i++)
		x[i] = i;
	k = 30;
	while (x[k] < (1 << T1)) {
		x[k + 1] = (x[k] * 27) / 26;
		k++;
	}
}

void InitDevice() {
	calcX();
}

static pair<int, int> calcP(long long t) {
	int lenX = x[t & ((1 << T2) - 1)];
	int st = (t >> T2);
	return {st, st + lenX - 1};
}

static bool inSub(pair<int, int> u, pair<int, int> v) {
	return u.first <= v.first && v.second <= u.second;
}

int Answer(long long S, long long T) {
	pair<int, int> x = calcP(S);
	pair<int, int> y = calcP(T);
	if (inSub(y, x))
		return 0;
	return inSub(x, y)? 1: 2;
}

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