Submission #39812

#	Time	Username	Problem	Language	Result	Execution time	Memory
39812		aome	Dungeon 2 (JOI16_dungeon2)	C++14	100 / 100	36 ms	3284 KiB

dungeon2

#include "dungeon2.h"
#include <bits/stdc++.h>

using namespace std;

typedef pair<int, int> ii;

const int N = 205;
const int INF = 0x3f3f3f3f;

const int pw3[] = {1, 3, 9, 27, 81}; 

int n, node;
int sz[N], par[N];
int edge[N][N], anc[N][N];
int bit3[N][5];
int dis[N][N], res[N];
vector<ii> G[N];

void dfs() {
	node = n++;
	int par_edge = LastRoad();
	sz[node] = NumberOfRoads();
	for (int i = 1; i <= sz[node]; ++i) {
		if (i == par_edge) continue;
		Move(i, 2);
		int color = Color();
		if (color > 1) {
			int tmp = LastRoad();
			Move(tmp, color);
			edge[node][i] = color;
		}
		else {
			par[n] = node, G[node].push_back(ii(n, i)), dfs();
		}
	}
	if (par_edge != -1) {
		Move(par_edge, 3), node = par[node];
	}
}

void dfs2(int u, int x) {
	int coloru = bit3[u][x] + 1;
	int par_edge;
	if (u) par_edge = LastRoad();
	for (int i = 1; i <= sz[u]; ++i) {
		if (edge[u][i] == 2) {
			Move(i, coloru);
			int colorp, last_road;
			colorp = Color(), anc[u][i] += pw3[x] * (colorp - 1);
			last_road = LastRoad(), Move(last_road, colorp);
		} 
	}
	for (auto i : G[u]) {
		Move(i.second, coloru), dfs2(i.first, x);
	}
	if (u) Move(par_edge, coloru);
} 

void Inspect(int R) {
	dfs();
	for (int i = 0; i < n; ++i) {
		int cur = i;
		for (int j = 0; j < 5; ++j) {
			bit3[i][j] = cur % 3, cur /= 3;
		}
	}
	for (int i = 0; i < 5; ++i) dfs2(0, i);
	memset(dis, INF, sizeof dis);
	for (int i = 0; i < n; ++i) {
		for (int j = 1; j <= sz[i]; ++j) {
			if (edge[i][j] == 2) G[i].push_back(ii(anc[i][j], j));
		}
		dis[i][i] = 0;
		for (auto j : G[i]) {
			dis[i][j.first] = dis[j.first][i] = 1;
		}
	}
	for (int k = 0; k < n; ++k) {
		for (int i = 0; i < n; ++i) {
			for (int j = 0; j < n; ++j) {
				dis[i][j] = min(dis[i][j], dis[i][k] + dis[k][j]);
			}
		}
	}
	for (int i = 0; i < n; ++i) {
		for (int j = 0; j < i; ++j) {
			res[dis[i][j]]++;
		}
	}
	for (int i = 1; i <= R; ++i) Answer(i, res[i]);
}

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