結果

問題 No.2606 Mirror Relay
ユーザー Jeroen Op de BeekJeroen Op de Beek
提出日時 2024-01-12 21:40:23
言語 C++17
(gcc 12.3.0 + boost 1.83.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
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 2 ms
6,816 KB
testcase_01 AC 2 ms
6,944 KB
testcase_02 AC 2 ms
6,940 KB
testcase_03 AC 2 ms
6,944 KB
testcase_04 AC 2 ms
6,940 KB
testcase_05 AC 2 ms
6,944 KB
testcase_06 AC 2 ms
6,944 KB
testcase_07 AC 2 ms
6,944 KB
testcase_08 AC 2 ms
6,944 KB
testcase_09 AC 3 ms
6,940 KB
testcase_10 AC 3 ms
6,940 KB
testcase_11 AC 2 ms
6,940 KB
testcase_12 AC 3 ms
6,940 KB
testcase_13 AC 2 ms
6,940 KB
testcase_14 AC 2 ms
6,944 KB
testcase_15 AC 2 ms
6,940 KB
testcase_16 AC 2 ms
6,944 KB
testcase_17 AC 2 ms
6,940 KB
testcase_18 AC 2 ms
6,940 KB
testcase_19 AC 2 ms
6,944 KB
testcase_20 AC 3 ms
6,940 KB
testcase_21 AC 2 ms
6,944 KB
testcase_22 AC 3 ms
6,940 KB
testcase_23 AC 2 ms
6,940 KB
testcase_24 AC 2 ms
6,944 KB
testcase_25 AC 3 ms
6,944 KB
testcase_26 AC 2 ms
6,940 KB
testcase_27 AC 3 ms
6,940 KB
testcase_28 AC 3 ms
6,944 KB
testcase_29 AC 3 ms
6,940 KB
testcase_30 AC 2 ms
6,940 KB
testcase_31 AC 2 ms
6,940 KB
testcase_32 AC 2 ms
6,940 KB
testcase_33 AC 2 ms
6,940 KB
testcase_34 AC 2 ms
6,944 KB
testcase_35 AC 2 ms
6,940 KB
testcase_36 AC 2 ms
6,944 KB
testcase_37 AC 2 ms
6,940 KB
testcase_38 AC 2 ms
6,944 KB
testcase_39 AC 10 ms
6,944 KB
testcase_40 AC 10 ms
6,944 KB
testcase_41 AC 10 ms
6,940 KB
testcase_42 AC 10 ms
6,940 KB
testcase_43 AC 10 ms
6,944 KB
testcase_44 AC 10 ms
6,944 KB
testcase_45 AC 10 ms
6,940 KB
testcase_46 AC 10 ms
6,940 KB
testcase_47 AC 10 ms
6,940 KB
testcase_48 AC 10 ms
6,944 KB
testcase_49 AC 18 ms
12,376 KB
testcase_50 AC 20 ms
13,368 KB
testcase_51 AC 19 ms
13,732 KB
testcase_52 AC 19 ms
13,244 KB
testcase_53 AC 20 ms
12,924 KB
testcase_54 AC 20 ms
13,032 KB
testcase_55 AC 27 ms
21,572 KB
testcase_56 AC 19 ms
12,576 KB
testcase_57 AC 20 ms
12,832 KB
testcase_58 AC 24 ms
20,836 KB
testcase_59 AC 10 ms
6,940 KB
testcase_60 AC 10 ms
6,940 KB
testcase_61 AC 10 ms
6,940 KB
testcase_62 AC 10 ms
6,944 KB
testcase_63 AC 11 ms
6,944 KB
testcase_64 AC 10 ms
6,940 KB
testcase_65 AC 10 ms
6,940 KB
testcase_66 AC 10 ms
6,940 KB
testcase_67 AC 10 ms
6,940 KB
testcase_68 AC 10 ms
6,940 KB
testcase_69 AC 39 ms
37,852 KB
testcase_70 AC 2 ms
5,376 KB
testcase_71 AC 2 ms
5,376 KB
testcase_72 AC 2 ms
5,376 KB
権限があれば一括ダウンロードができます

ソースコード

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