oj.uz

Submission #684273

# Submission time Handle Problem Language Result Execution time Memory
684273 2023-01-20T19:34:26 Z rainboy City (JOI17_city) C++17
78 / 100
 526 ms 111280 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 - 1);
			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 37 ms 74956 KB Output is correct
2 Correct 37 ms 74956 KB Output is correct
3 Correct 37 ms 74948 KB Output is correct
4 Correct 38 ms 74932 KB Output is correct
5 Correct 40 ms 74956 KB Output is correct
6 Correct 37 ms 74956 KB Output is correct
7 Correct 37 ms 74904 KB Output is correct
8 Correct 43 ms 74860 KB Output is correct
9 Correct 44 ms 75084 KB Output is correct
10 Correct 41 ms 75044 KB Output is correct
11 Correct 39 ms 74924 KB Output is correct
12 Correct 38 ms 74920 KB Output is correct

Subtask #2
70.0 / 92.0

# Verdict Execution time Memory Grader output
1 Partially correct 296 ms 83444 KB Output is partially correct - L = 643379917
2 Partially correct 286 ms 83596 KB Output is partially correct - L = 643250992
3 Partially correct 289 ms 83536 KB Output is partially correct - L = 643379917
4 Partially correct 287 ms 83480 KB Output is partially correct - L = 643379917
5 Partially correct 507 ms 110824 KB Output is partially correct - L = 1171476901
6 Partially correct 494 ms 110936 KB Output is partially correct - L = 1171476901
7 Partially correct 526 ms 111120 KB Output is partially correct - L = 1171476901
8 Partially correct 494 ms 110068 KB Output is partially correct - L = 1171476901
9 Partially correct 475 ms 111136 KB Output is partially correct - L = 1171476901
10 Partially correct 456 ms 111164 KB Output is partially correct - L = 1171476901
11 Partially correct 454 ms 111180 KB Output is partially correct - L = 1171476901
12 Partially correct 450 ms 111280 KB Output is partially correct - L = 1171476901
13 Partially correct 479 ms 111120 KB Output is partially correct - L = 1171476901
14 Partially correct 506 ms 111164 KB Output is partially correct - L = 1171476901
15 Partially correct 288 ms 83484 KB Output is partially correct - L = 643379917
16 Partially correct 284 ms 83464 KB Output is partially correct - L = 643379917
17 Partially correct 285 ms 83472 KB Output is partially correct - L = 643379917
18 Partially correct 458 ms 110756 KB Output is partially correct - L = 1171476901
19 Partially correct 461 ms 110804 KB Output is partially correct - L = 1171476901
20 Partially correct 500 ms 110772 KB Output is partially correct - L = 1171476901
21 Partially correct 483 ms 110828 KB Output is partially correct - L = 1171476901
22 Partially correct 479 ms 110788 KB Output is partially correct - L = 1171476901
23 Partially correct 486 ms 110628 KB Output is partially correct - L = 1171476901
24 Partially correct 480 ms 110716 KB Output is partially correct - L = 1171476901
25 Partially correct 480 ms 110652 KB Output is partially correct - L = 1171476901
26 Partially correct 494 ms 110556 KB Output is partially correct - L = 1171476901
27 Partially correct 485 ms 110420 KB Output is partially correct - L = 1171476901