Submission #21023

#	Time	Username	Problem	Language	Result	Execution time	Memory
21023		model_code	City (JOI17_city)	C++11	100 / 100	598 ms	57936 KiB

Encoder

#include "Encoder.h"

#include <vector>
using namespace std;

const int kMaxN = 250000;
const int kMaxDepth = 18;
const double kRatio = 1.05;

static vector<int> graph[kMaxN];
static vector<int> widths;

static int lf[kMaxN], rg[kMaxN], last_id;

void SetWidths()
{
	int w = 1;
	widths.push_back((int)w);
	int times = kMaxDepth + 1;
	while (times > 0) {
		int w2 = w * kRatio;
		if (w == w2) ++w2;
		widths.push_back(w2);
		if (w2 > kMaxN) {
			--times;
		}
		w = w2;
	}
}

int ceiling(int w)
{
	return *(lower_bound(widths.begin(), widths.end(), w));
}

void visit(int p, int rt)
{
	lf[p] = last_id++;
	for (int q : graph[p]) if (q != rt) {
		visit(q, p);
	}
	rg[p] = last_id = lf[p] + ceiling(last_id - lf[p]);
}

void Encode(int N, int A[], int B[])
{
	SetWidths();
	for (int i = 0; i < N - 1; ++i) {
		graph[A[i]].push_back(B[i]);
		graph[B[i]].push_back(A[i]);
	}
	last_id = 0;
	visit(0, -1);
	for (int i = 0; i < N; ++i) {
		int wc = lower_bound(widths.begin(), widths.end(), rg[i] - lf[i]) - widths.begin();
		long long code = (long long)lf[i] * widths.size() + wc;
		Code(i, code);
	}
}

Device

#include "Device.h"

#include <algorithm>
#include <vector>
#include <cstdio>
using namespace std;

const int kMaxN = 250000;
const int kMaxDepth = 18;
const double kRatio = 1.05;

static vector<int> widths;

void InitDevice()
{
	int w = 1;
	widths.push_back((int)w);
	int times = kMaxDepth + 1;
	while (times > 0) {
		int w2 = w * kRatio;
		if (w == w2) ++w2;
		widths.push_back(w2);
		if (w2 > kMaxN) {
			--times;
		}
		w = w2;
	}
}

pair<int, int> range(long long code)
{
	int left = (int)(code / widths.size());
	int w = widths[(int)(code % widths.size())];
	return{ left, left + w };
}

int Answer(long long S, long long T)
{
	pair<int, int> X = range(S), Y = range(T);
	if (Y.first <= X.first && X.second <= Y.second) return 0;
	if (X.first <= Y.first && Y.second <= X.second) return 1;
	return 2;
}

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