Submission #27173

#	Time	Username	Problem	Language	Result	Execution time	Memory
27173		abcdef6199	Dungeon 2 (JOI16_dungeon2)	C++98	100 / 100	36 ms	4904 KiB

dungeon2

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

typedef long long LL;
typedef pair<int, int> II;

const int MAXN = 500 + 10;
int n, a[MAXN][MAXN];
int ans[MAXN][MAXN];
vector<II> adj[MAXN];
vector<int> ret[MAXN];

void Build(int u) {
	int deg = NumberOfRoads();
	int pre = LastRoad();
	for (int i = 1; i <= deg; ++i) if (i != pre) {
		Move(i, 2);
		int x = LastRoad();
		if (Color() == 1) {
			adj[u].push_back(II(++n, i));
			Build(n);
			Move(x, 3);
		}
		else {
			int c = Color();
			if (c == 2) ret[u].push_back(i);
			Move(x, c);
		}
	}
}

void DFS(int u, int pw, vector<int> ver) {
	int h = (int) ver.size();
	for (int j = 0; j < (int) ret[u].size(); ++j) {
		int i = ret[u][j];
		Move(i, h % (pw * 3) / pw + 1);
		int x = LastRoad();
		int c = Color();
		ans[u][i] += pw * (c - 1);
		Move(x, c);
		if (pw == 81) {
			assert(ans[u][i] < (int) ver.size());
			int v = ver[ans[u][i]];
			a[u][v] = 1;
			a[v][u] = 1;
		}
	}
	ver.push_back(u);
	for (int j = 0; j < (int) adj[u].size(); ++j) {
		int i = adj[u][j].second;
		Move(i, h % (pw * 3) / pw + 1);
		int x = LastRoad();
		DFS(adj[u][j].first, pw, ver);
		Move(x, Color());
	}
	ver.pop_back();
}

void Inspect(int R) {
	n = 1; Build(1);
	for (int i = 1; i <= n; ++i) {
		for (int j = 1; j <= n; ++j) a[i][j] = 100000;
		a[i][i] = 0;
	}
	for (int i = 1; i <= n; ++i) {
		for (int j = 0; j < (int) adj[i].size(); ++j) {
			int x = adj[i][j].first;
			a[i][x] = 1;
			a[x][i] = 1;
		}
	}
	DFS(1,  1, vector<int>(0, 0));
	DFS(1,  3, vector<int>(0, 0));
	DFS(1,  9, vector<int>(0, 0));
	DFS(1, 27, vector<int>(0, 0));
	DFS(1, 81, vector<int>(0, 0));

	for (int k = 1; k <= n; ++k)
		for (int i = 1; i <= n; ++i)
			for (int j = 1; j <= n; ++j)
				a[i][j] = min(a[i][j], a[i][k] + a[k][j]);
	for (int i = 1; i <= R; ++i) {
		int ans = 0;
		for (int u = 1; u <= n; ++u)
			for (int v = u + 1; v <= n; ++v)
				if (a[u][v] == i) ans++;
		Answer(i, ans);
	}
}

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