結果

問題 No.2606 Mirror Relay
ユーザー Jeroen Op de BeekJeroen Op de Beek
提出日時 2024-01-12 21:40:23
言語 C++17(gcc12)
(gcc 12.3.0 + boost 1.87.0)
結果
AC  
実行時間 39 ms / 2,000 ms
コード長 2,383 bytes
コンパイル時間 2,439 ms
コンパイル使用メモリ 206,252 KB
実行使用メモリ 37,852 KB
最終ジャッジ日時 2024-09-27 21:37:50
合計ジャッジ時間 4,900 ms
ジャッジサーバーID
（参考情報） 		judge4 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 69
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include "bits/stdc++.h"
using namespace std;
#define all(x) begin(x),end(x)
template<typename A, typename B> ostream& operator<<(ostream &os, const pair<A, B> &p) { return os << '(' << p.first << ", " << p.second << ')'; }
template<typename T_container, typename T = typename enable_if<!is_same<T_container, string>::value, typename T_container::value_type>::type> ostream& operator<<(ostream &os, const T_container &v) { string sep; for (const T &x : v) os << sep << x, sep = " "; return os; }
#define debug(a) cerr << "(" << #a << ": " << a << ")\n";
typedef long long ll;
typedef vector<int> vi;
typedef vector<vi> vvi;
typedef pair<int,int> pi;
const int mxN = 1e5+1, oo = 1e9;
const int SIG = 26;
const char firstC = 'a';
struct smallmap {
    int to[SIG] = {};
    int& operator[](char c) {
        return to[c-firstC];
    }
};
struct eertree {

    struct node {
        smallmap to;
        // can store extra stuff!
        int len,link,occ;

        ll best=0;
    };
    vector<node> nd = {{},{}};
    string s = "$";
    int at=1,n=1;
    eertree() {
        nd[0].len=-1;
    }
    bool good(int at, char c) {
        return s[n-1-nd[at].len]==c;
    }
    void addNode(int p, char c) {
        int nw = nd.size();
        nd.push_back({});
        nd[nw].len=nd[p].len+2;
        auto& lnk = nd[nw].link = nd[p].link;
        while(lnk and !good(lnk,c)) lnk = nd[lnk].link;
        lnk = nd[lnk].to[c];
        lnk+=!lnk;
        nd[p].to[c]=nw;
    }
    void add(char c) {
        s.push_back(c);
        
        while(true) {
            if(good(at,c)) {
                if(!nd[at].to[c]) addNode(at,c);
                at = nd[at].to[c];
                break;
            } else at = nd[at].link; 
            // if rollbacking is needed, don't traverse suffix links in a dumb way.
        }
        n++;
        nd[at].occ++;
        
    }
    ll findbest() {
        ll best=0;
        for(int i=nd.size()-1;i>1;--i) {
            nd[nd[i].link].occ+=nd[i].occ;
            best = max(best,nd[i].len*ll(nd[i].occ));
        }
        
        for(int i=1;i<nd.size();++i) {
            nd[i].best= max(nd[i].best,nd[nd[i].link].best+nd[i].len*ll(nd[i].occ));
            best=max(best,nd[i].best);
        }
        return best;
    }
};
int main() {
    string s; cin >> s;
    eertree et;
    for(auto c : s) et.add(c);
    cout << et.findbest() << '\n';
}
0