oj.uz

Submission #684272

# Submission time Handle Problem Language Result Execution time Memory
684272 2023-01-20T19:28:29 Z rainboy City (JOI17_city) C++17
8 / 100
 292 ms 83540 KB 
#include "Encoder.h"
#include <stdlib.h>

static const int N = 250000, H = 18;

static int len[N + 1][H + 1], offset[N + 1][H + 1];

static void InitEncoder() {
	for (int n = 1; n <= N; n++)
		for (int h = 0; h <= H; h++)
			len[n][h] = n * (h + 1);
	int x = 0;
	for (int n = 1; n <= N; n++)
		for (int h = 0; h <= H; h++)
			offset[n][h] = x, x += len[N][H] / n;
}

static int *ej[N], eo[N], sz[N], hh[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, int h) {
	sz[i] = 1, hh[i] = h;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			dfs1(i, j, h);
			sz[i] += sz[j];
		}
	}
}

static void dfs2(int p, int i, int x) {
	Code(i, offset[sz[i]][hh[i]] + x / sz[i]);
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p) {
			x = (x + sz[j] - 1) / sz[j] * sz[j];
			dfs2(i, j, x), x += len[sz[j]][hh[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, H);
	dfs2(-1, 0, 0);
}
#include "Device.h"
 
static const int N = 250000, H = 18;
 
static int len[N + 1][H + 1], offset[N + 1][H + 1];

void InitDevice() {
	for (int n = 1; n <= N; n++)
		for (int h = 0; h <= H; h++)
			len[n][h] = n * (h + 1);
	int x = 0;
	for (int n = 1; n <= N; n++)
		for (int h = 0; h <= H; h++)
			offset[n][h] = x, x += len[N][H] / n;
}

static void Decode(long long x, int *a, int *b) {
	int lower = 1 * (H + 1) + 0, upper = (N + 1) * (H + 1);

	while (upper - lower > 1) {
		int nh = (lower + upper) / 2, n = nh / (H + 1), h = nh % (H + 1);

		if (x < offset[n][h])
			upper = nh;
		else
			lower = nh;
	}
	int nh = lower, n = nh / (H + 1), h = nh % (H + 1);
	*a = (x - offset[n][h]) * n, *b = *a + len[n][h];
}

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

Encoder.cpp: In function 'void append(int, int)':
Encoder.cpp:22:23: warning: suggest parentheses around '-' in operand of '&' [-Wparentheses]
   22 |  if (o >= 2 && (o & o - 1) == 0)
      |                     ~~^~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 74968 KB Output is correct
2 Correct 40 ms 74980 KB Output is correct
3 Correct 44 ms 74892 KB Output is correct
4 Correct 40 ms 74944 KB Output is correct
5 Correct 38 ms 75084 KB Output is correct
6 Correct 40 ms 75076 KB Output is correct
7 Correct 39 ms 74884 KB Output is correct
8 Correct 38 ms 74928 KB Output is correct
9 Correct 39 ms 75196 KB Output is correct
10 Correct 37 ms 74956 KB Output is correct
11 Correct 38 ms 75232 KB Output is correct
12 Correct 41 ms 75008 KB Output is correct

Subtask #2
0 / 92.0

# Verdict Execution time Memory Grader output
1 Incorrect 292 ms 83540 KB Wrong Answer [6]
2 Halted 0 ms 0 KB -