Submission #684179

#	Time	Username	Problem	Language	Result	Execution time	Memory
684179		rainboy	City (JOI17_city)	C++17	22 / 100	378 ms	50596 KiB

Encoder

#include "Encoder.h"
#include <stdlib.h>

static const int N = 250000;

static int *ej[N], eo[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 int ta[N], tb[N], time;

static void dfs(int p, int i) {
	ta[i] = time++;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p)
			dfs(i, j);
	}
	tb[i] = time;
}

void Encode(int n, int ii[], int jj[]) {
	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]);
	time = 0, dfs(-1, 0);
	for (int i = 0; i < n; i++)
		Code(i, (long long) ta[i] * (N + 1) + tb[i]);
}

Device

#include "Device.h"

static const int N = 250000;

void InitDevice() {}

int Answer(long long x, long long y) {
	int tai = x / (N + 1), tbi = x % (N + 1), taj = y / (N + 1), tbj = y % (N + 1);
	if (taj <= tai && tbi <= tbj)
		return 0;
	if (tai <= taj && tbj <= tbi)
		return 1;
	return 2;
}

Compilation message (stderr)

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

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