結果
問題 |
No.3196 Unique Nickname
|
ユーザー |
|
提出日時 | 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 |
ソースコード
#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; }