Submission #711368

#	Time	Username	Problem	Language	Result	Execution time	Memory
711368		rainboy	Amusement Park (JOI17_amusement_park)	C++14	8 / 100	37 ms	19200 KiB

Joi

#include "Joi.h"
#include <stdlib.h>
#include <string.h>

static const int N = 10000, L = 60;

static int *ej[N], eo[N], ii_[N][L], uu_[N][L], vv_[N][L];

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 cc[N], n_, m_;

static bool dfs1(int i) {
	ii_[0][cc[i] = n_++] = i;
	if (n_ == L)
		return true;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			bool done = dfs1(j);
			uu_[0][m_] = cc[i], vv_[0][m_] = cc[j], m_++;
			if (done)
				return true;
		}
	}
	return false;
}

static int dd[L];

static void extend(int i, int j) {
	memset(dd, 0, L * sizeof *dd);
	memcpy(ii_[j], ii_[i], L * sizeof *ii_[i]);
	memcpy(uu_[j], uu_[i], (L - 1) * sizeof *uu_[i]);
	memcpy(vv_[j], vv_[i], (L - 1) * sizeof *vv_[i]);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[j][h], v = vv_[j][h];
		dd[u]++, dd[v]++;
	}
	int a = cc[i];
	for (int b = 0; b < L - 1; b++)
		if (b != cc[i] && dd[b] == 1) {
			ii_[j][cc[j] = b] = j;
			for (int h = 0; h < L - 1; h++) {
				int u = uu_[j][h], v = vv_[j][h];
				if (u == b || v == b) {
					uu_[j][h] = a, vv_[j][h] = b;
					return;
				}
			}
		}
}

static void dfs2(int i) {
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			extend(i, j);
			dfs2(j);
		}
	}
}

static void alloc_(int n) {
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
}

static void free_(int n) {
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

static void precalc(int *uu, int *vv, int n, int m) {
	for (int h = 0; h < m; h++)
		append(uu[h], vv[h]), append(vv[h], uu[h]);
	memset(cc, -1, n * sizeof *cc);
	n_ = 0, m_ = 0, dfs1(0);
	for (int a = 1; a < L; a++) {
		int i = ii_[0][a];
		memcpy(ii_[i], ii_[0], L * sizeof *ii_[0]);
		memcpy(uu_[i], uu_[0], (L - 1) * sizeof *uu_[0]);
		memcpy(vv_[i], vv_[0], (L - 1) * sizeof *vv_[0]);
	}
	for (int a = 0; a < L; a++) {
		int i = ii_[0][a];
		dfs2(i);
	}
}

void Joi(int n, int m, int *uu, int *vv, long long x, int t) {
	t = t;
	alloc_(n);
	precalc(uu, vv, n, m);
	for (int i = 0; i < n; i++)
		MessageBoard(i, x >> cc[i] & 1);
	free_(n);
}

Ioi

#include "Ioi.h"
#include <stdlib.h>
#include <string.h>

static const int N = 10000, L = 60;

static int *ej[N], eo[N], ii_[N][L], uu_[N][L], vv_[N][L];

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 cc[N], n_, m_;

static bool dfs1(int i) {
	ii_[0][cc[i] = n_++] = i;
	if (n_ == L)
		return true;
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			bool done = dfs1(j);
			uu_[0][m_] = cc[i], vv_[0][m_] = cc[j], m_++;
			if (done)
				return true;
		}
	}
	return false;
}

static int dd[L];

static void extend(int i, int j) {
	memset(dd, 0, L * sizeof *dd);
	memcpy(ii_[j], ii_[i], L * sizeof *ii_[i]);
	memcpy(uu_[j], uu_[i], (L - 1) * sizeof *uu_[i]);
	memcpy(vv_[j], vv_[i], (L - 1) * sizeof *vv_[i]);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[j][h], v = vv_[j][h];
		dd[u]++, dd[v]++;
	}
	int a = cc[i];
	for (int b = 0; b < L - 1; b++)
		if (b != cc[i] && dd[b] == 1) {
			ii_[j][cc[j] = b] = j;
			for (int h = 0; h < L - 1; h++) {
				int u = uu_[j][h], v = vv_[j][h];
				if (u == b || v == b) {
					uu_[j][h] = a, vv_[j][h] = b;
					return;
				}
			}
		}
}

static void dfs2(int i) {
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (cc[j] == -1) {
			extend(i, j);
			dfs2(j);
		}
	}
}

static void alloc_(int n) {
	for (int i = 0; i < n; i++)
		ej[i] = (int *) malloc(2 * sizeof *ej[i]), eo[i] = 0;
}

static void free_(int n) {
	for (int i = 0; i < n; i++)
		free(ej[i]);
}

static void precalc(int *uu, int *vv, int n, int m) {
	for (int h = 0; h < m; h++)
		append(uu[h], vv[h]), append(vv[h], uu[h]);
	memset(cc, -1, n * sizeof *cc);
	n_ = 0, m_ = 0, dfs1(0);
	for (int a = 1; a < L; a++) {
		int i = ii_[0][a];
		memcpy(ii_[i], ii_[0], L * sizeof *ii_[0]);
		memcpy(uu_[i], uu_[0], (L - 1) * sizeof *uu_[0]);
		memcpy(vv_[i], vv_[0], (L - 1) * sizeof *vv_[0]);
	}
	for (int a = 0; a < L; a++) {
		int i = ii_[0][a];
		dfs2(i);
	}
}

static long long x;

static void dfs3(int p, int i, int z) {
	x |= (long long) z << cc[i];
	for (int o = eo[i]; o--; ) {
		int j = ej[i][o];
		if (j != p)
			dfs3(i, j, Move(j)), Move(i);
	}
}

long long Ioi(int n, int m, int *uu, int *vv, int s, int z, int t) {
	t = t;
	alloc_(n);
	precalc(uu, vv, n, m);
	free_(n);
	alloc_(n);
	for (int h = 0; h < L - 1; h++) {
		int u = uu_[s][h], v = vv_[s][h], u_ = ii_[s][u], v_ = ii_[s][v];
		append(u_, v_), append(v_, u_);
	}
	x = 0;
	dfs3(-1, s, z);
	return x;
}

Compilation message (stderr)

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

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

• Subtask 1: 8 / 8
• Subtask 2: 0 / 10
• Subtask 3: 0 / 10
• Subtask 4: 0 / 55
• Subtask 5: 0 / 17