oj.uz

답안 #685247

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
685247 2023-01-23T18:02:13 Z rainboy City (JOI17_city) C++17
100 / 100
 407 ms 49552 KB 
/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4-city-review.pdf */
#include "Encoder.h"
#include <stdlib.h>

static const int N = 250000, N_ = 601654, H = 18;
static const double B = 1.05;

static int len[N + 1], m;

static void InitEncoder() {
	m = 0;
	len[0] = 1;
	while (len[m] <= N_)
		len[m + 1] = (int) ((len[m] + 1) * B), m++;
}

static int lg(int n) {
	int lower = -1, upper = m;
	while (upper - lower > 1) {
		int h = (lower + upper) / 2;
		if (len[h] >= n)
			upper = h;
		else
			lower = h;
	}
	return upper;
}

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

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, 0);
}
/* https://www.ioi-jp.org/camp/2017/2017-sp-tasks/2017-sp-d4-city-review.pdf */
#include "Device.h"

static const int N = 250000, N_ = 601654, H = 18;
static const double B = 1.05;

static int len[N + 1];

void InitDevice() {
	int m = 0;
	len[0] = 1;
	while (len[m] <= N_)
		len[m + 1] = (int) ((len[m] + 1) * B), m++;
}

int Answer(long long x, long long y) {
	int ta1 = x % N_, tb1 = ta1 + len[x / N_];
	int ta2 = y % N_, tb2 = ta2 + len[y / N_];
	if (ta2 <= ta1 && tb1 <= tb2)
		return 0;
	if (ta1 <= ta2 && tb2 <= tb1)
		return 1;
	return 2;
}

Compilation message

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

Subtask #1
8.0 / 8.0

# 결과 실행 시간 메모리 Grader output
1 Correct 0 ms 528 KB Output is correct
2 Correct 0 ms 616 KB Output is correct
3 Correct 0 ms 528 KB Output is correct
4 Correct 1 ms 608 KB Output is correct
5 Correct 0 ms 528 KB Output is correct
6 Correct 1 ms 536 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 1 ms 536 KB Output is correct
9 Correct 0 ms 532 KB Output is correct
10 Correct 1 ms 608 KB Output is correct
11 Correct 0 ms 528 KB Output is correct
12 Correct 0 ms 536 KB Output is correct

Subtask #2
92.0 / 92.0

# 결과 실행 시간 메모리 Grader output
1 Correct 154 ms 16024 KB Output is correct - L = 50538936
2 Correct 193 ms 16056 KB Output is correct - L = 51140590
3 Correct 150 ms 16036 KB Output is correct - L = 50538936
4 Correct 163 ms 16036 KB Output is correct - L = 50538936
5 Correct 402 ms 49108 KB Output is correct - L = 124542378
6 Correct 380 ms 49076 KB Output is correct - L = 124542378
7 Correct 353 ms 49096 KB Output is correct - L = 124542378
8 Correct 383 ms 48360 KB Output is correct - L = 126347340
9 Correct 377 ms 49500 KB Output is correct - L = 130558918
10 Correct 312 ms 49452 KB Output is correct - L = 131762226
11 Correct 334 ms 49480 KB Output is correct - L = 132363880
12 Correct 341 ms 49552 KB Output is correct - L = 132363880
13 Correct 333 ms 49260 KB Output is correct - L = 127550648
14 Correct 350 ms 49068 KB Output is correct - L = 125745686
15 Correct 156 ms 16132 KB Output is correct - L = 51140590
16 Correct 150 ms 16036 KB Output is correct - L = 50538936
17 Correct 207 ms 16080 KB Output is correct - L = 50538936
18 Correct 328 ms 48696 KB Output is correct - L = 131762226
19 Correct 407 ms 48652 KB Output is correct - L = 131762226
20 Correct 330 ms 48748 KB Output is correct - L = 131762226
21 Correct 346 ms 48920 KB Output is correct - L = 131160572
22 Correct 338 ms 48828 KB Output is correct - L = 131160572
23 Correct 330 ms 48856 KB Output is correct - L = 131160572
24 Correct 397 ms 48848 KB Output is correct - L = 130558918
25 Correct 340 ms 49012 KB Output is correct - L = 129957264
26 Correct 332 ms 48600 KB Output is correct - L = 129355610
27 Correct 362 ms 48876 KB Output is correct - L = 128753956