#1167591 (C++23) No.2020 Sum of Common Prefix Length

• 問題: No.2020 Sum of Common Prefix Length
• ユーザー: kuhaku
• 提出日時: 2026-05-29 22:33:29
• 言語: C++23 (gcc 15.2.0 + boost 1.89.0)
• 結果: TLE
• 実行時間: -
• コード長: 3,865 bytes
• コンパイル時間: 1,480 ms
• コンパイル使用メモリ: 169,856 KB
• 実行使用メモリ: 50,236 KB
• 最終ジャッジ日時: 2026-05-29 22:34:19
• 合計ジャッジ時間: 11,314 ms
• ジャッジサーバーID （参考情報）: judge3_1 / judge4_0

ファイルパターン	結果
other	AC * 26 TLE * 1 -- * 11

ソースコード

// competitive-verifier: PROBLEM https://yukicoder.me/problems/no/2020
#include <cstdint>
#include <iostream>
#include <string>
#include <vector>
#include <cassert>
/// @brief Trie
/// @see https://algo-logic.info/trie-tree/
/// @see https://atcoder.jp/contests/tenka1-2016-final-open/tasks/tenka1_2016_final_c
template <int char_size = 96, int base = ' '>
struct Trie {
  private:
    struct _node {
        std::vector<int> next_node;
        int count;  ///< このノードを通過した文字列の本数（= このノードに対応する接頭辞を持つ文字列数）
        _node() : next_node(char_size, -1), count(0) {}
    };
  public:
    using node_type = _node;
    Trie() : root(0), nodes() { nodes.emplace_back(); }
    int size() const { return nodes.size(); }
    /// @brief ノード node_id の子 c をたどる。無ければ新規作成。count は更新しない。
    /// @return 子ノードの id
    int add(int node_id, char ch) {
        assert(0 <= node_id && node_id < (int)nodes.size());
        int c = ch - base;
        assert(0 <= c && c < char_size);
        int &next_id = nodes[node_id].next_node[c];
        if (next_id == -1) {
            next_id = nodes.size();
            nodes.emplace_back();
        }
        return next_id;
    }
    /// @brief ノード node_id の通過カウントを増やす。
    void add_count(int node_id, int x = 1) {
        assert(0 <= node_id && node_id < (int)nodes.size());
        nodes[node_id].count += x;
    }
    /// @brief ノード node_id の通過カウント（接頭辞を持つ文字列数）。
    int count(int node_id) const {
        assert(0 <= node_id && node_id < (int)nodes.size());
        return nodes[node_id].count;
    }
    std::vector<int> insert(const std::string &word) {
        std::vector<int> res;
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = nodes[node_id].next_node[c];
            if (next_id == -1) {
                next_id = nodes.size();
                nodes.emplace_back();
            }
            node_id = next_id;
            ++nodes[node_id].count;
            res.emplace_back(node_id);
        }
        return res;
    }
    int search_id(const std::string &word) {
        int node_id = 0;
        for (int i = 0; i < (int)word.size(); ++i) {
            int c = word[i] - base;
            int &next_id = nodes[node_id].next_node[c];
            if (next_id == -1) return -1;
            node_id = next_id;
        }
        return node_id;
    }
    node_type get_node(int node_id) const {
        assert(0 <= node_id && node_id < (int)nodes.size());
        return nodes[node_id];
    }
  private:
    int root;
    std::vector<node_type> nodes;
};
// S_x と全 S_k の最長共通接頭辞長の総和は、S_x が通る Trie のパス上の
// 各ノードの「通過文字列数(count)」の総和に等しい。
int main() {
    int n;
    std::cin >> n;
    Trie<26, 'a'> trie;
    std::vector<std::vector<int>> path(n);  ///< path[i]: S_i がたどるノード id 列
    for (int i = 0; i < n; ++i) {
        std::string s;
        std::cin >> s;
        path[i] = trie.insert(s);
    }
    int q;
    std::cin >> q;
    while (q--) {
        int type;
        std::cin >> type;
        if (type == 1) {
            int x;
            char c;
            std::cin >> x >> c;
            --x;
            int parent = path[x].empty() ? 0 : path[x].back();
            int nid = trie.add(parent, c);
            trie.add_count(nid);
            path[x].emplace_back(nid);
        } else {
            int x;
            std::cin >> x;
            --x;
            std::uint64_t ans = 0;
            for (int nid : path[x]) ans += trie.count(nid);
            std::cout << ans << '\n';
        }
    }
    return 0;
}