Submission #695244

#	Time	Username	Problem	Language	Result	Execution time	Memory
695244		rainboy	Dungeon 2 (JOI16_dungeon2)	C++17	100 / 100	16 ms	1124 KiB

dungeon2

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

const int N = 200, L = 5;	/* L = ceil(log3(N + 1)) */

int pp3[L + 1];

void init() {
	pp3[0] = 1;
	for (int l = 1; l <= L; l++)
		pp3[l] = pp3[l - 1] * 3;
}

int *ej[N + 1], eo[N + 1], ff[N + 1], n; char *et[N + 1];

void dfs1(int i) {
	eo[i] = NumberOfRoads();
	ej[i] = (int *) malloc((eo[i] + 1) * sizeof *ej[i]);
	et[i] = (char *) malloc((eo[i] + 1) * sizeof *et[i]);
	ff[i] = LastRoad();
	for (int o = 1; o <= eo[i]; o++)
		if (o != ff[i]) {
			Move(o, 2);
			if (Color() == 1) {
				int j = ++n;
				ej[i][o] = j, et[i][o] = 0, dfs1(j), Move(ff[j], 3);
			} else if (Color() == 2)
				ej[i][o] = 0, et[i][o] = 1, Move(LastRoad(), Color());
			else
				ej[i][o] = 0, et[i][o] = 2, Move(LastRoad(), Color());
		} else
			ej[i][o] = 0, et[i][o] = 2;
}

void dfs2(int i, int l) {
	for (int o = 1; o <= eo[i]; o++) {
		int j = ej[i][o], t = et[i][o];
		if (t == 0)
			Move(o, i / pp3[l] % 3 + 1), dfs2(j, l), Move(ff[j], j / pp3[l] % 3 + 1);
		else if (t == 1)
			Move(o, i / pp3[l] % 3 + 1), ej[i][o] += pp3[l] * (Color() - 1), Move(LastRoad(), Color());
	}
}

int dd[N + 1], ans[N + 1];

void bfs(int s) {
	static int qu[N + 1];
	for (int i = 1; i <= n; i++)
		dd[i] = n;
	int cnt = 0;
	dd[s] = 0, qu[cnt++] = s;
	for (int h = 0; h < cnt; h++) {
		int i = qu[h], d = dd[i] + 1;
		for (int o = 1; o <= eo[i]; o++) {
			int j = ej[i][o];
			if (dd[j] > d)
				dd[j] = d, qu[cnt++] = j;
		}
	}
}

void find_graph() {
	n = 1, dfs1(1);
	for (int l = 0; l < L; l++)
		dfs2(1, l);
	for (int i = 1; i <= n; i++)
		for (int o = 1; o <= eo[i]; o++)
			if (et[i][o] == 0 || et[i][o] == 1) {
				int j = ej[i][o];
				for (int o_ = 1; o_ <= eo[j]; o_++)
					if (et[j][o_] == 2) {
						et[j][o_] = -1, ej[j][o_] = i;
						break;
					}
			}
}

void Inspect(int d_) {
	init();
	find_graph();
	memset(ans, 0, (n + 1) * sizeof *ans);
	for (int i = 1; i <= n; i++) {
		bfs(i);
		for (int j = i + 1; j <= n; j++)
			ans[dd[j]]++;
	}
	for (int d = 1; d <= d_; d++)
		Answer(d, ans[d]);
}

• Subtask 1: 17 / 17
• Subtask 2: 27 / 27
• Subtask 3: 56 / 56