結果

問題 No.3196 Unique Nickname
コンテスト
ユーザー elphe
提出日時 2025-07-11 23:09:22
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 6,117 bytes
コンパイル時間 1,058 ms
コンパイル使用メモリ 92,800 KB
実行使用メモリ 7,844 KB
最終ジャッジ日時 2025-07-11 23:09:24
合計ジャッジ時間 2,018 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <cstdint>
#include <array>
#include <vector>

using namespace std;

template<uint32_t base = 'a', uint32_t letter_kinds = 26>
class Trie
{
	struct Node
	{
		const uint32_t from, letter;
		uint32_t count_as_prefix = 0;
		uint32_t count_as_same = 0;
		array<uint32_t, letter_kinds> next_as = { };

		constexpr Node(const uint32_t from, const uint32_t letter) noexcept : from(from), letter(letter) { }
	};

protected:
	vector<Node> nodes;

	constexpr void disable_all_below(const uint32_t index) noexcept
	{
		nodes[index].count_as_prefix = nodes[index].count_as_same = 0;
		for (uint32_t i = 0; i != letter_kinds; ++i)
			if (nodes[index].next_as[i] != 0)
				disable_all_below(nodes[index].next_as[i]);
	}

public:
	constexpr Trie() : nodes(1, Node(0, UINT32_MAX)) { }
	constexpr Trie(const uint32_t reservation) : nodes(1, Node(0, UINT32_MAX)) { nodes.reserve(reservation); }

	constexpr const Node& operator[](const uint32_t index) const noexcept
	{
		return nodes[index];
	}

	constexpr uint32_t index_of(const string& S, const bool phantom_mode = false) noexcept
	{
		uint32_t cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
			if ((cur = nodes[cur].next_as[S[i] - base]) == 0)
				return UINT32_MAX;

		if (phantom_mode || nodes[cur].count_as_prefix != 0)
			return cur;
		else
			return UINT32_MAX;
	}

	constexpr void add_word(const string& S) noexcept
	{
		uint32_t cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			++nodes[cur].count_as_prefix;
			if (nodes[cur].next_as[S[i] - base] == 0)
				nodes[cur].next_as[S[i] - base] = nodes.size(), nodes.emplace_back(cur, S[i] - base);
			cur = nodes[cur].next_as[S[i] - base];
		}

		++nodes[cur].count_as_prefix, ++nodes[cur].count_as_same;
	}

	constexpr uint32_t remove_word(const string& S, const bool all_remove_mode = true) noexcept
	{
		const uint32_t remove_count = all_remove_mode ? count_word(S) : 1;
		if (remove_count == 0 || (all_remove_mode && count_word(S) == 0)) return 0;

		uint32_t cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			nodes[cur].count_as_prefix -= remove_count;
			cur = nodes[cur].next_as[S[i] - base];
		}

		nodes[cur].count_as_prefix -= remove_count;
		nodes[cur].count_as_same -= remove_count;
		return remove_count;
	}

	constexpr uint32_t remove_prefix(const string& prefix) noexcept
	{
		const uint32_t remove_count = count_prefix(prefix);
		if (remove_count == 0) return 0;

		uint32_t cur = 0;
		for (uint32_t i = 0; i != prefix.size(); ++i)
		{
			nodes[cur].count_as_prefix -= remove_count;
			cur = nodes[cur].next_as[prefix[i] - base];
		}

		disable_all_below(cur);
		return remove_count;
	}

	constexpr uint32_t remove_prefix_of(const string& S) noexcept
	{
		uint32_t remove_count = 0, cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			remove_count += nodes[cur].count_as_same;
			nodes[cur].count_as_prefix -= nodes[cur].count_as_same;
			nodes[cur].count_as_same = 0;

			cur = nodes[cur].next_as[S[i] - base];
		}

		return remove_count;
	}

	constexpr uint32_t count_word(const string& S) const noexcept
	{
		uint32_t cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
			if ((cur = nodes[cur].next_as[S[i] - base]) == 0)
				return 0;

		return nodes[cur].count_as_same;
	}

	constexpr uint32_t count_prefix(const string& prefix) const noexcept
	{
		uint32_t cur = 0;
		for (uint32_t i = 0; i != prefix.size(); ++i)
			if ((cur = nodes[cur].next_as[prefix[i] - base]) == 0)
				return 0;

		return nodes[cur].count_as_prefix;
	}

	constexpr uint32_t count_prefix_of(const string& S) const noexcept
	{
		uint32_t count = 0, cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			count += nodes[cur].count_as_same;
			if ((cur = nodes[cur].next_as[S[i] - base]) == 0)
				return count;
		}

		return count += nodes[cur].count_as_same;
	}

	constexpr uint32_t count_until(const string& S) const noexcept
	{
		uint32_t count = 0, cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			for (uint32_t j = 0; j != (S[i] - base); ++j)
				if (nodes[cur].next_as[j] != 0)
					count += nodes[nodes[cur].next_as[j]].count_as_prefix;

			if ((cur = nodes[cur].next_as[S[i] - base]) == 0)
				return count;
		}

		return count += nodes[cur].count_as_same;
	}

	constexpr uint32_t count_after(const string& S) const noexcept
	{
		uint32_t count = 0, cur = 0;
		for (uint32_t i = 0; i != S.size(); ++i)
		{
			for (uint32_t j = letter_kinds - 1; j != (S[i] - base); --j)
				if (nodes[cur].next_as[j] != 0)
					count += nodes[nodes[cur].next_as[j]].count_as_prefix;

			if ((cur = nodes[cur].next_as[S[i] - base]) == 0)
				return count;
		}

		return count += nodes[cur].count_as_prefix - nodes[cur].count_as_same;
	}

	constexpr string search_kth_word(const uint32_t index) const noexcept
	{
		uint32_t count = 0, cur = 0;
		string result = ""s;

		if ((count += nodes[cur].count_as_prefix) <= index)
			return ""s;

		while (1)
		{
			uint32_t i = letter_kinds;
			while (--i != UINT32_MAX)
			{
				if (nodes[cur].next_as[i] != 0)
					continue;
				if (count <= index + nodes[nodes[cur].next_as[i]].count_as_prefix)
				{
					result += base + i;
					cur = nodes[cur].next_as[i];
					break;
				}
				else
					count -= nodes[nodes[cur].next_as[i]].count_as_prefix;
			}

			if (i == UINT32_MAX)
				return result;
		}
	}

	constexpr void reserve(const uint32_t reservation) { nodes.reserve(reservation); }
	constexpr uint32_t size() const noexcept { return nodes[0].count_as_prefix; }
};

static inline constexpr const char* solve(const uint_fast32_t N, const vector<string>& S, const vector<string>& T) noexcept
{
	Trie names(15 * N);
	for (uint_fast32_t i = 0; i != N; ++i)
		names.add_word(S[i]), names.add_word(T[i]);

	for (uint_fast32_t i = 0; i != N; ++i)
		if (names.count_word(S[i]) > 1 && names.count_word(T[i]) > 1)
			return "No";

	return "Yes";
}

int main()
{
	std::cin.tie(nullptr);
	std::ios::sync_with_stdio(false);
	
	uint_fast32_t N, i;
	std::cin >> N;
	vector<string> S(N), T(N);
	for (i = 0; i != N; ++i)
	{
		S[i].reserve(15), T[i].reserve(15);
		cin >> S[i] >> T[i];
	}

	std::cout << solve(N, S, T) << '\n';
	return 0;
}
0