Submission #134901

#	Time	Username	Problem	Language	Result	Execution time	Memory
134901		imyujin	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	24 ms	1784 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>
using namespace std;

const int MAXN = 205;

static int N;
static int K[MAXN], par[MAXN], parroad[MAXN];
static vector<int> te[MAXN], ne[MAXN], ed[MAXN];			// te => 1 : par, 2 : chi, 3 : back edge, 4 : ancestor
static int thr[6];
static int dis[MAXN][MAXN], cnt[MAXN];

void dfs(int x) {
	K[x] = NumberOfRoads();
	parroad[x] = LastRoad();
	te[x].resize(K[x] + 1);
	ne[x].resize(K[x] + 1, 0);
	if(parroad[x] != -1) {
		te[x][parroad[x]] = 1;
		ne[x][parroad[x]] = par[x];
	}
	for(int i = 1; i <= K[x]; i++) if(te[x][i] != 1) {
		Move(i, 2);
		if(Color() == 1) {
			te[x][i] = 2;
			ne[x][i] = ++N;
			par[N] = x;
			dfs(N);
		}
		else if(Color() == 2) {
			te[x][i] = 3;
			Move(LastRoad(), 2);
		}
		else {
			te[x][i] = 4;
			Move(LastRoad(), 3);
		}
	}
	if(parroad[x] != -1) Move(parroad[x], 3);
}

void solve(int x, int k) {
	//printf("solve(x = %d, k = %d)\n", x, k);
	for(int i = 1; i <= K[x]; i++) {
		if(te[x][i] == 2) {
			Move(i, x / thr[k] % 3 + 1);
			solve(ne[x][i], k);
		}
		else if(te[x][i] == 3) {
			Move(i, 1);
			int c = Color();
			ne[x][i] = ne[x][i] * 3 + c - 1;
			Move(LastRoad(), c);
		}
	}
	if(parroad[x] != -1) Move(parroad[x], x / thr[k] % 3 + 1);
}

void Inspect(int R) {
	N = 1;
	dfs(1);

	thr[0] = 1;
	for(int i = 1; i < 6; i++) thr[i] = thr[i - 1] * 3;
	for(int i = 4; i >= 0; i--) solve(1, i);

	for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++) dis[i][j] = i == j ? 0 : N;
	for(int i = 1; i <= N; i++) for(int j = 1; j <= K[i]; j++) if(te[i][j] % 2) {
		ed[i].push_back(ne[i][j]);
		ed[ne[i][j]].push_back(i);
		dis[i][ne[i][j]] = dis[ne[i][j]][i] = 1;
	}
	/*
	for(int i = 1; i <= N; i++) {
		printf("i = %d\n", i);
		for(int j = 1; j <= K[i]; j++) printf("te = %d, ne = %d\n", te[i][j], ne[i][j]);
	}
	*/
	for(int k = 1; k <= N; k++) for(int i = 1; i <= N; i++) for(int j = 1; j <= N; j++)
		dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);

	for(int i = 1; i <= N; i++) for(int j = 1; j < i; j++) cnt[dis[i][j]]++;
	for(int i = 1; i <= R; i++) Answer(i, cnt[i]);
}

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