Submission #684267

#	Time	Username	Problem	Language	Result	Execution time	Memory
684267		rainboy	City (JOI17_city)	C++17	8 / 100	203 ms	13072 KiB

Encoder

#include "Encoder.h"
#include <stdlib.h>
 
static const int N = 250000;
 
static int len[N + 1], offset[N + 1];
 
static void InitEncoder() {
	len[1] = 1;
	for (int n = 2, l = 0; n <= N; n++) {
		while (1 << l + 1 <= n)
			l++;
		len[n] = n * (l + 1);
	}
	offset[0] = 0;
	for (int n = 1; n <= N; n++)
		offset[n] = offset[n - 1] + len[N] / n;
}
 
static int *ej[N], eo[N], sz[N];
 
static void append(int i, int j) {
	int o = eo[i]++;
	if (o >= 2 && (o & o - 1) == 0)
		ej[i] = (int *) realloc(ej[i], o * 2 * sizeof *ej[i]);
	ej[i][o] = j;
}
 
static void dfs1(int p, int i) {
	sz[i] = 1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			dfs1(i, j);
			sz[i] += sz[j];
		}
	}
}
 
static void dfs2(int p, int i, int x) {
	Code(i, offset[sz[i] - 1] + x / sz[i]);
	int j_ = -1;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p && (j_ == -1 || sz[j_] < sz[j]))
			j_ = j;
	}
	if (j_ != -1)
		dfs2(i, j_, x), x += len[sz[j_]];
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p && j != j_) {
			x = (x + sz[j] - 1) / sz[j] * sz[j];
			dfs2(i, j, x), x += len[sz[j]];
		}
	}
}
 
void Encode(int n, int *ii, int *jj) {
	InitEncoder();
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]);
	for (int h = 0; h < n - 1; h++)
		append(ii[h], jj[h]), append(jj[h], ii[h]);
	dfs1(-1, 0);
	dfs2(-1, 0, 0);
}

Device

#include "Device.h"
 
static const int N = 250000;
 
static int len[N + 1], offset[N + 1];
 
void InitDevice() {
	len[1] = 1;
	for (int n = 2, l = 0; n <= N; n++) {
		while (1 << l + 1 <= n)
			l++;
		len[n] = n * (l + 1);
	}
	offset[0] = 0;
	for (int n = 1; n <= N; n++)
		offset[n] = offset[n - 1] + len[N] / n;
}
 
static void Decode(long long x, int *a_, int *b_) {
	int lower = 0, upper = N + 1;
	while (upper - lower > 1) {
		int n = (lower + upper) / 2;
		if (x >= offset[n])
			lower = n;
		else
			upper = n;
	}
	int n = upper;
	*a_ = (x - offset[n - 1]) * n, *b_ = *a_ + len[n];
}
 
int Answer(long long x, long long y) {
	int tai, tbi, taj, tbj;
	Decode(x, &tai, &tbi), Decode(y, &taj, &tbj);
	if (taj <= tai && tbi <= tbj)
		return 0;
	if (tai <= taj && tbj <= tbi)
		return 1;
	return 2;
}

Compilation message (stderr)

Encoder.cpp: In function 'void InitEncoder()':
Encoder.cpp:11:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   11 |   while (1 << l + 1 <= n)
      |               ~~^~~
Encoder.cpp: In function 'void append(int, int)':
Encoder.cpp:24:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   24 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

Device.cpp: In function 'void InitDevice()':
Device.cpp:10:17: warning: suggest parentheses around '+' inside '<<' [-Wparentheses]
   10 |   while (1 << l + 1 <= n)
      |               ~~^~~

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