#946932 (C++17(gcc12)) No.2606 Mirror Relay

• 問題: No.2606 Mirror Relay
• ユーザー: rogi52
• 提出日時: 2024-01-27 02:54:20
• 言語: C++17(gcc12) (gcc 12.3.0 + boost 1.87.0)
• 結果: AC
• 実行時間: 68 ms / 2,000 ms
• コード長: 9,472 bytes
• コンパイル時間: 8,572 ms
• コンパイル使用メモリ: 276,128 KB
• 最終ジャッジ日時: 2025-02-19 00:05:44
• ジャッジサーバーID （参考情報）: judge3 / judge5

ファイルパターン	結果
sample	AC * 4
other	AC * 69

ソースコード

#line 2 "cp-library/src/cp-template.hpp"
#include <bits/stdc++.h>
using namespace std;
using ll = long long;
using ld = long double;
using uint = unsigned int;
using ull  = unsigned long long;
using i32 = int;
using u32 = unsigned int;
using i64 = long long;
using u64 = unsigned long long;
using i128 = __int128_t;
template < class T > bool chmin(T& a, T b) { if(a > b) { a = b; return true; } return false; }
template < class T > bool chmax(T& a, T b) { if(a < b) { a = b; return true; } return false; }
template < class T, class U > T ceil (T x, U y) { return (x > 0 ? (x + y - 1) / y :           x / y); }
template < class T, class U > T floor(T x, U y) { return (x > 0 ?           x / y : (x - y + 1) / y); }
int popcnt(i32 x) { return __builtin_popcount(x); }
int popcnt(u32 x) { return __builtin_popcount(x); }
int popcnt(i64 x) { return __builtin_popcountll(x); }
int popcnt(u64 x) { return __builtin_popcountll(x); }

#line 2 "cp-library/src/utility/rep_itr.hpp"
template < class T > struct itr_rep {
    T i, d;
    constexpr itr_rep(const T i) noexcept : i(i), d(1) {}
    constexpr itr_rep(const T i, const T d) noexcept : i(i), d(d) {}
    void operator++() noexcept { i += d; }
    constexpr int operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr_rep x) const noexcept { return d > 0 ? i < x.i : i > x.i; }
};

template < class T > struct rep {
    const itr_rep< T > s, t;
    constexpr rep(const T t) noexcept : s(0), t(t) {}
    constexpr rep(const T s, const T t) noexcept : s(s), t(t) {}
    constexpr rep(const T s, const T t, const T d) noexcept : s(s, d), t(t, d) {}
    constexpr auto begin() const noexcept { return s; }
    constexpr auto end  () const noexcept { return t; }
};

template < class T > struct revrep {
    const itr_rep < T > s, t;
    constexpr revrep(const T t) noexcept : s(t - 1, -1), t(-1, -1) {}
    constexpr revrep(const T s, const T t) noexcept : s(t - 1, -1), t(s - 1, -1) {}
    constexpr revrep(const T s, const T t, const T d) noexcept : s(t - 1, -d), t(s - 1, -d) {}
    constexpr auto begin() const noexcept { return s; }
    constexpr auto end  () const noexcept { return t; }
};
#line 3 "cp-library/src/utility/io.hpp"

/* 128bit integer */
istream& operator>>(istream& is, i128& x) {
    std::string s; is >> s;
    int pm = (s[0] == '-');
    x = 0;
    for(int i : rep(pm, int(s.size()))) x = x * 10 + (s[i] - '0');
    if(pm) x *= -1;
    return is;
}
ostream& operator<<(ostream& os, const i128& x) {
    if(x == 0) return os << '0';
    i128 y = x;
    if(y < 0) {
        os << '-';
        y *= -1;
    }
    std::vector<int> ny;
    while(y > 0) {
        ny.push_back(y % 10);
        y /= 10;
    }
    for(int i : revrep(ny.size())) os << ny[i];
    return os;
}

namespace scanner {
    struct sca {
        template < class T > operator T() {
            T s; std::cin >> s; return s;
        }
    };
    struct vec {
        int n;
        vec(int n) : n(n) {}
        template < class T > operator std::vector< T >() {
            std::vector< T > v(n);
            for(T& x : v) std::cin >> x;
            return v;
        }
    };
    struct mat {
        int h, w;
        mat(int h, int w) : h(h), w(w) {}
        template < class T > operator std::vector< std::vector< T > >() {
            std::vector m(h, std::vector< T >(w));
            for(std::vector< T >& v : m) for(T& x : v) std::cin >> x;
            return m;
        }
    };
    struct speedup {
        speedup() {
            std::cin.tie(0);
            std::ios::sync_with_stdio(0);
        }
    } speedup_instance;
}
scanner::sca in() { return scanner::sca(); }
scanner::vec in(int n) { return scanner::vec(n); }
scanner::mat in(int h, int w) { return scanner::mat(h, w); }

namespace printer {
    void precision(int d) { std::cout << std::fixed << std::setprecision(d); }
    void flush() { std::cout.flush(); }
}

template < class T >
ostream& operator<<(ostream& os, const std::vector< T > a) {
    int n = a.size();
    for(int i : rep(n)) { os << a[i]; if(i != n - 1) os << ' '; }
    return os;
}

int print() { std::cout << '\n'; return 0; }
template < class head, class... tail > int print(head&& h, tail&&... t) {
    std::cout << h; if(sizeof...(tail)) std::cout << ' ';
    return print(std::forward<tail>(t)...);
}
template < class T > int print_n(const std::vector< T > a) {
    int n = a.size();
    for(int i : rep(n)) std::cout << a[i] << "\n";
    return 0;
}


#line 2 "cp-library/src/utility/key_val.hpp"

template < class K, class V >
struct key_val {
    K key; V val;
    key_val() {}
    key_val(K key, V val) : key(key), val(val) {}
    template < std::size_t Index >
    std::tuple_element_t< Index, key_val >& get() {
        if constexpr (Index == 0) return key;
        if constexpr (Index == 1) return val;
    }
};

namespace std {

template < class K, class V > struct tuple_size < key_val< K, V > > : integral_constant< size_t, 2 > {};
template < class K, class V > struct tuple_element < 0, key_val< K, V > > { using type = K; };
template < class K, class V > struct tuple_element < 1, key_val< K, V > > { using type = V; };

}
#line 2 "cp-library/src/utility/vec_op.hpp"
template < class T > key_val< int, T > max_of(const vector< T >& a) {
    int i = std::max_element(a.begin(), a.end()) - a.begin();
    return {i, a[i]};
}
template < class T > key_val< int, T > min_of(const vector< T >& a) {
    int i = std::min_element(a.begin(), a.end()) - a.begin();
    return {i, a[i]};
}
template < class S, class T > S sum_of(const vector< T >& a) {
    S sum = 0;
    for(const T x : a) sum += x;
    return sum;
}
template < class S, class T > vector< S > freq_of(const vector< T >& a, T L, T R) {
    vector< S > res(R - L, S(0));
    for(const T x : a) res[x - L] += 1;
    return res;
}
template < class S, class T > struct prefix_sum {
    vector< S > s;
    prefix_sum(const vector< T >& a) : s(a) {
        s.insert(s.begin(), S(0));
        for(int i : rep(a.size())) s[i + 1] += s[i];
    }
    // [L, R)
    S sum(int L, int R) { return s[R] - s[L]; }
};
#line 3 "cp-library/src/utility/heap.hpp"

template < class T > using heap_min = std::priority_queue< T, std::vector< T >, std::greater< T > >;
template < class T > using heap_max = std::priority_queue< T, std::vector< T >, std::less< T > >;

#line 27 "cp-library/src/cp-template.hpp"

#line 1 "cp-library/src/algorithm/bin_search.hpp"
template < class T, class F >
T bin_search(T ok, T ng, F f) {
    while(abs(ok - ng) > 1) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}

template < class T, class F >
T bin_search_real(T ok, T ng, F f, int step = 80) {
    while(step--) {
        T mid = (ok + ng) / 2;
        (f(mid) ? ok : ng) = mid;
    }
    return ok;
}
#line 2 "cp-library/src/algorithm/argsort.hpp"

template < class T > std::vector< int > argsort(const std::vector< T > &a) {
    std::vector< int > ids((int)a.size());
    std::iota(ids.begin(), ids.end(), 0);
    std::sort(ids.begin(), ids.end(), [&](int i, int j) {
        return a[i] < a[j] || (a[i] == a[j] && i < j);
    });
    return ids;
}
#line 2 "eertree.cpp"

template < class char_type >
struct eertree {
    using size_type = int;
    struct node_type {
        map<char_type, size_type> nxt;
        size_type link, len, count;

        node_type(size_type link, size_type len, size_type count) : link(link), len(len), count(count) {}
    };

    size_type lsp;
    vector<char_type> s;
    vector<node_type> g;

    eertree() : lsp(0) {
        g.emplace_back(0, -1, 0); // odd
        g.emplace_back(0,  0, 0); // even
    }

    // return node(c + str(?) + c)
    size_type find(size_type v) const {
        const size_type n = s.size() - 1;
        while(true) {
            size_type i = n - g[v].len - 1;
            if(0 <= i and s[i] == s[n]) return v;
            v = g[v].link;
        }
    }

    void push_back(char_type c) {
        s.push_back(c);
        size_type v = find(lsp);

        if(g[v].nxt.contains(c)) {
            lsp = g[v].nxt[c];
            g[lsp].count++;
        } else {
            lsp = g[v].nxt[c] = g.size();
            g.emplace_back(v == 0 ? 1 : g[find(g[v].link)].nxt[c], 1 + g[v].len + 1, 1);
        }
    }

    vector<size_type> freq() {
        vector<size_type> freq(g.size(), 0);
        for(size_type i = size_type(g.size()) - 1; i > 0; i--) {
            freq[i] += g[i].count;
            freq[g[i].link] += freq[i];
        }
        return freq;
    }

    string str(size_type v) {
        if(v == 0) return "odd(-1)";
        if(v == 1) return "even(0)";
        string res = "";
        function<bool(size_type)> dfs = [&](size_type x) -> bool {
            if(x == v) return true;
            for(auto [c, nx] : g[x].nxt) {
                if(dfs(nx)) {
                    res.push_back(c);
                    return true;
                }
            }
            return false;
        }; dfs(0); dfs(1);
        string rr = res; reverse(rr.begin(), rr.end());
        if(g[v].len % 2 == 1) rr.pop_back();
        return res + rr;
    }
};

int main() {
    string S = in();
    eertree<char> ete;
    for(char c : S) ete.push_back(c);
    vector<int> freq = ete.freq();

    auto tree = ete.g;
    const int n = tree.size();
    vector<i64> dp(n, 0);
    for(int i : rep(2, n)) {
        int pi = tree[i].link;
        chmax(dp[i], dp[pi] + 1LL * freq[i] * tree[i].len);
    }
    print(max_of(dp).val);
}