提出 #65346915

---

ソースコード 拡げる

#line 2 "Library/Common.hpp"

/**
 * @file Common.hpp
 */

#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <cstdint>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <limits>
#include <map>
#include <numeric>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <tuple>
#include <utility>
#include <vector>
using namespace std;

using ll = int64_t;
using ull = uint64_t;

constexpr const ll INF = (1LL << 62) - (3LL << 30) - 1;
#line 2 "Library/Tree/Tree.hpp"

#line 2 "Library/Graph/Graph.hpp"

#line 4 "Library/Graph/Graph.hpp"

using Vertex = int;

template<typename CostType = int32_t>
struct Edge{
    public:
    Edge() = default;

    Edge(Vertex from_, Vertex to_, CostType cost_ = 1, int idx_ = -1) :
        from(from_), to(to_), cost(cost_), idx(idx_){}
    
    bool operator<(const Edge<CostType> &e) const {return cost < e.cost;}

    operator int() const {return to;}

    Vertex from, to;
    CostType cost;
    int idx;
};

template<typename CostType = int32_t>
class Graph{
    public:
    Graph() = default;

    Graph(int n) : vertex_size_(n), edge_size_(0), adjacent_list_(n){}
    
    inline void AddUndirectedEdge(Vertex u, Vertex v, CostType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<CostType>(u, v, w, idx));
        adjacent_list_[v].push_back(Edge<CostType>(v, u, w, idx));
    }
    
    inline void AddDirectedEdge(Vertex u, Vertex v, CostType w = 1){
        int idx = edge_size_++;
        adjacent_list_[u].push_back(Edge<CostType>(u, v, w, idx));
    }

    inline size_t VertexSize() const {
        return vertex_size_;
    }

    inline size_t EdgeSize() const {
        return edge_size_;
    }

    inline vector<Edge<CostType>> &operator[](const int v){
        return adjacent_list_[v];
    }

    inline const vector<Edge<CostType>> &operator[](const int v) const {
        return adjacent_list_[v];
    }
    
    private:
    size_t vertex_size_, edge_size_;
    vector<vector<Edge<CostType>>> adjacent_list_;
};

template<typename CostType = int32_t>
Graph<CostType> InputGraph(int N, int M, int padding = -1, bool weighted = false, bool directed = false){
    Graph<CostType> G(N);
    for(int i = 0; i < M; ++i){
        Vertex u, v; CostType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        if(directed) G.AddDirectedEdge(u, v, w);
        else G.AddUndirectedEdge(u, v, w);
    }
    return G;
}
#line 4 "Library/Tree/Tree.hpp"

template<typename CostType = int32_t>
Graph<CostType> InputTree(int N, int padding = -1, bool weighted = false){
    Graph<CostType> G(N);
    for(int i = 0; i < N - 1; ++i){
        Vertex u, v; CostType w = 1;
        cin >> u >> v, u += padding, v += padding;
        if(weighted) cin >> w;
        G.AddUndirectedEdge(u, v, w);
    }
    return G;
}

template<typename CostType>
vector<int> CalculateTreeParent(Graph<CostType> &T, Vertex r = 0){
    int n = T.VertexSize();
    vector<int> ret(n, -1);
    auto rec = [&](auto &self, Vertex u) -> void {
        for(Vertex v : T[u]){
            if(v == ret[u]) continue;
            ret[v] = u;
            self(self, v);
        }
    };
    rec(rec, r);
    return ret;
}

template<typename CostType>
vector<int> CalculateTreeDepth(Graph<CostType> &T, Vertex r = 0){
    int n = T.VertexSize();
    vector<int> ret(n, 0);
    auto rec = [&](auto &self, Vertex u, Vertex p, int d) -> void {
        ret[u] = d;
        for(Vertex v : T[u]){
            if(v == p) continue;
            self(self, v, u, d + 1);
        }
    };
    rec(rec, r, -1, 0);
    return ret;
}

template<typename CostType>
vector<CostType> CalculateTreeDistance(Graph<CostType> &T, Vertex r = 0){
    int n = T.VertexSize();
    vector<CostType> ret(n, CostType(INF));
    auto rec = [&](auto &self, Vertex u) -> void {
        for(const Edge<CostType> &e : T[u]){
            if(ret[e.to] > ret[u] + e.cost){
                ret[e.to] = ret[u] + e.cost;
                self(self, e.to);
            }
        }
    };
    ret[r] = 0;
    rec(rec, r);
    return ret;
}

// /**
//  * @brief 各頂点を根とする部分木のサイズを求める。
//  * @param tree 木
//  * @return vector<int> 各頂点を根とする部分木のサイズ
//  */
// template<typename CostType>
// vector<int> CalculateSubtreeSize(RootedTree<CostType> &tree){
//     Vertex root = tree.get_root();
//     int V = tree.get_vertex_size();
//     vector<int> ret(V, 1);
//     auto rec = [&](auto self, Vertex v) -> int {
//         for(Vertex u : tree.get_child(v)){
//             ret[v] += self(self, u);
//         }
//         return ret[v];
//     };
//     rec(rec, root);
//     return ret;
// }

// /**
//  * @brief 各頂点を行きかけ順に並べたときに何番目に相当するかの配列を求める。
//  * @param tree 木
//  * @return vector<int> 各頂点が行きかけ順で何番目になるか (0-index)
//  */
// template<typename CostType>
// vector<int> CalculatePreOrder(RootedTree<CostType> &tree){
//     Vertex root = tree.get_root();
//     int V = tree.get_vertex_size(), time_stamp = 0;
//     vector<int> ret(V, -1);
//     auto rec = [&](auto self, Vertex v) -> void {
//         ret[v] = time_stamp++;
//         for(Vertex u : tree.get_child()){
//             self(self, u);
//         }
//     };
//     rec(rec, root);
//     return ret;
// }
#line 3 "Library/String/Trie.hpp"

template<int MAXSIZE = 500010>
class Trie{
    public:
    Trie(vector<string> &S_) : S(S_), n((int)S_.size()), v(1), vertex_(n), child_(MAXSIZE){
        for(int i = 0; i < MAXSIZE; ++i){
            child_[i].fill(-1);
        }
        for(int i = 0; i < n; ++i){
            int p = 0, m = S[i].size();
            vertex_[i].resize(m + 1, 0);
            for(int j = 0; j < m; ++j){
                int c = S[i][j] - 'a';
                if(child_[p][c] == -1){
                    child_[p][c] = v++;
                }
                p = child_[p][c];
                vertex_[i][j + 1] = p;
            }
        }
    }

    Graph<int32_t> Build() const {
        Graph<int32_t> ret(v);
        for(int i = 0; i < v; ++i){
            for(int j = 0; j < 26; ++j){
                if(child_[i][j] == -1) continue;
                ret.AddUndirectedEdge(i, child_[i][j]);
            }
        }
        return ret;
    }

    vector<int> &operator[](const int i){
        return vertex_[i];
    }

    private:
    vector<string> &S;
    int n, v;
    vector<vector<int>> vertex_;
    vector<array<int, 26>> child_;
};
#line 2 "code.cpp"

int main(){
    int N; cin >> N;
    vector<string> S(N);
    for(int i = 0; i < N; ++i) cin >> S[i];

    Trie<300010> trie(S);
    auto T = trie.Build();
    int n = T.VertexSize();
    vector<int> cnt(n, 0);
    ll ans = 0;
    for(int i = 0; i < N; ++i){
        for(int j = 1; j < trie[i].size(); ++j){
            ans += cnt[trie[i][j]];
            cnt[trie[i][j]] += 1;
        }
    }
    cout << ans << endl;
}

提出情報

コンパイルエラー

code.cpp: In function ‘int main()’:
code.cpp:14:26: warning: comparison of integer expressions of different signedness: ‘int’ and ‘std::vector<int>::size_type’ {aka ‘long unsigned int’} [-Wsign-compare]

ジャッジ結果