結果

問題 No.2606 Mirror Relay
コンテスト
ユーザー miscalc
提出日時 2025-10-24 04:47:37
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 34 ms / 2,000 ms
コード長 3,112 bytes
コンパイル時間 3,802 ms
コンパイル使用メモリ 288,748 KB
実行使用メモリ 34,748 KB
最終ジャッジ日時 2025-10-24 04:47:44
合計ジャッジ時間 5,958 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using pll = pair<ll, ll>;
#define vc vector
using vl = vc<ll>;

#define ov(a, b, c, name, ...) name
#define rep2(i, l, r) for(ll i = (l); i < ll(r); i++)
#define rep1(i, n) rep2(i, 0, n)
#define rep(...) ov(__VA_ARGS__, rep2, rep1)(__VA_ARGS__)
#define fec(...) for(const auto& __VA_ARGS__)
#define per(i, a, b) for(ll i = ll(a) - 1; i >= ll(b); i--)

#define ALL(x) begin(x), end(x)
#define SZ(x) (ll) size(x)
#define LB(v, x) (lower_bound(ALL(v), x) - begin(v))
#define eb emplace_back

bool chmin(auto& a, auto b) { return a > b ? a = b, 1 : 0; }
bool chmax(auto& a, auto b) { return a < b ? a = b, 1 : 0; }
const ll INF = ll(4e18) + 100;

void printvec(const auto& v) {
   for(auto it = begin(v); it != end(v); it++) cout << *it << " ";
   cout << endl;
}

#ifdef LOCAL
#define local(...) __VA_ARGS__
#else
#define local(...)
#endif

// 頂点: ODD (0), EVEN (1), 含まれる回文
// 順辺 (par, chi): 両側に 1 文字足してできる回文への辺
// 逆辺 (suf): 最大回文接尾辞への辺, EVEN -> ODD
template<int C = 26, char first = 'a'> struct Eertree {
   string s;
   vc<int> len{-1, 0}, suf{0, 0}, par{0, 0}, vs;
   vc<array<int, C>> chi;
   int cur = 1;  // 現在の文字列の最大回文接尾辞の頂点番号
   Eertree() : chi(2) { rep(i, 2) fill(ALL(chi[i]), -1); }
   int findpar(int v) {
      for(int i = s.size() - 1;; v = suf[v]) {
         int j = i - 1 - len[v];
         if(j >= 0 && s[j] == s[i]) return v;
      }
   }
   void add(char ch) {
      s += ch;
      int j = ch - first, p = findpar(cur), v = chi[p][j];
      if(v != -1) {
         vs.eb(cur = v);
         return;
      }
      vs.eb(chi[p][j] = cur = len.size());
      len.eb(len[p] + 2), par.eb(p);
      suf.eb(p == 0 ? 1 : chi[findpar(suf[p])][j]);
      chi.eb(), fill(ALL(chi.back()), -1);
   }
   // 各回文の出現回数
   vl count() {
      int n = len.size();
      vl cnt(n);
      fec(v : vs) cnt[v]++;
      per(i, n, 1) cnt[suf[i]] += cnt[i];
      return cnt;
   }
};

void main2()
{
  string S;
  cin >> S;
  Eertree et;
  fec(c : S) et.add(c);
  auto cnt = et.count();

  local(
        cout << et.s << endl;

        auto dfs = [&](auto &&dfs, ll v, string s) -> void
        {
          cout << v << " " << s << " " << cnt.at(v) << endl;
          rep(c, 26)
          {
            ll nv = et.chi.at(v).at(c);
            if (nv == -1)
              continue;
            string t = string(1, c + 'a');
            string ns = v == 0 ? t : t + s + t;
            dfs(dfs, nv, ns);
          }
        };
        dfs(dfs, 0, "");
        dfs(dfs, 1, "");

    );

    ll n = et.par.size();
    vl dp(n);
    rep(i, n) dp.at(i) = et.len.at(i) * cnt.at(i);
    per(i, n, 1)
    {
      ll j = et.suf.at(i);
      chmax(dp.at(j), dp.at(i) + et.len.at(j) * cnt.at(j));
    }
    ll ans = max(dp.at(0), dp.at(1));
    cout<<ans<<endl;
}

int main() {
#ifndef LOCAL
   cin.tie(0)->sync_with_stdio(0), cout.tie(0);
#endif

   local(while(true)) {
      ll t = 1;
      // cin >> t;
      while(t--) main2();
   }
}
0