Submission #349650

#	Time	Username	Problem	Language	Result	Execution time	Memory
349650		KoD	Dungeon 2 (JOI16_dungeon2)	C++17	44 / 100	17 ms	748 KiB

dungeon2

#include "dungeon2.h"

#include <vector>
#include <queue>
#include <utility>
#include <algorithm>
#include <iostream>

template <class T>
using Vec = std::vector<T>;

using Path = Vec<std::pair<int, int>>;

Vec<Vec<int>> graph;

void Inspect(int R) {
	Vec<int> ret(R + 1);
	Vec<Path> nodes;
	{
		std::queue<Path> que;
		que.push({ });
		while (!que.empty()) {
			const auto path = que.front();
			que.pop();
			nodes.push_back(path);
			const auto len = (int) path.size();
			if (len <= R) {
				ret[len] += 1;
			}
			for (int i = 0; i < len; ++i) {
				Move(path[i].first, 2);
			}
			const auto deg = NumberOfRoads();
			for (int i = 1; i <= deg; ++i) {
				Move(i, 2);
				if (Color() == 1) {
					auto new_path = path;
					new_path.emplace_back(i, LastRoad());
					que.push(new_path);
				}
				Move(LastRoad(), 2);
			}
			for (int i = len - 1; i >= 0; --i) {
				Move(path[i].second, 2);
			}
		}
	}
	for (int src = 1; src < (int) nodes.size(); ++src) {
		const auto Cur = Color();
		const auto Next = 3 - Cur;
		for (int i = 0; i < (int) nodes[src].size(); ++i) {
			Move(nodes[src][i].first, Cur);
		}
		std::queue<Path> que;
		que.push({ });
		while (!que.empty()) {
			const auto path = que.front();
			que.pop();
			const auto len = (int) path.size();
			if (len <= R) {
				ret[len] += 1;
			}
			for (int i = 0; i < len; ++i) {
				Move(path[i].first, Next);
			}
			const auto deg = NumberOfRoads();
			for (int i = 1; i <= deg; ++i) {
				Move(i, Next);
				if (Color() == Cur) {
					auto new_path = path;
					new_path.emplace_back(i, LastRoad());
					que.push(new_path);
				}
				Move(LastRoad(), Next);
			}
			for (int i = len - 1; i >= 0; --i) {
				Move(path[i].second, Next);
			}
		}
		for (int i = (int) nodes[src].size() - 1; i >= 0; --i) {
			Move(nodes[src][i].second, Next);
		}
	}
	for (int i = 1; i <= R; ++i) {
		Answer(i, ret[i] / 2);
	}
}

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