oj.uz

Submission #349650

# Submission time Handle Problem Language Result Execution time Memory
349650 2021-01-18T05:52:36 Z KoD None (JOI16_dungeon2) C++17
44 / 100
 17 ms 748 KB 
#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.0 / 17.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 492 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 364 KB Output is correct
7 Correct 2 ms 492 KB Output is correct
8 Correct 1 ms 364 KB Output is correct
9 Correct 2 ms 640 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 1 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 1 ms 512 KB Output is correct

Subtask #2
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 364 KB Output is correct
2 Correct 1 ms 492 KB Output is correct
3 Correct 1 ms 492 KB Output is correct
4 Correct 1 ms 492 KB Output is correct
5 Correct 1 ms 492 KB Output is correct
6 Correct 1 ms 492 KB Output is correct
7 Correct 1 ms 364 KB Output is correct
8 Correct 2 ms 492 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 2 ms 492 KB Output is correct
11 Correct 2 ms 492 KB Output is correct
12 Correct 2 ms 492 KB Output is correct
13 Correct 2 ms 492 KB Output is correct
14 Correct 1 ms 492 KB Output is correct
15 Correct 1 ms 512 KB Output is correct

Subtask #3
0 / 56.0

# Verdict Execution time Memory Grader output
1 Incorrect 17 ms 748 KB Output isn't correct
2 Halted 0 ms 0 KB -