Submission #1129325

#	Time	Username	Problem	Language	Result	Execution time	Memory
1129325		Hamed_Ghaffari	Palindromes (APIO14_palindrome)	C++20	47 / 100	37 ms	46920 KiB

palindrome

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

#define SZ(x) int(x.size())
#define pb push_back
#define all(x) x.begin(), x.end()
#define maxs(a, b) (a = max(a,b))

const int MXN = 3e5+5;

struct node {
    int ch[26], suflnk, sz;
    node() { memset(ch, -1, sizeof(ch)); suflnk=0; sz=0;}
} tree[MXN];
// 0 : -1, 1 : 0

int N = 2;
int id[MXN], dp[MXN];
vector<int> g[MXN];

void dfs(int v) {
    for(int u : g[v]) {
        dfs(u);
        dp[v] += dp[u];
    }
}

int32_t main() {
    cin.tie(0); cout.tie(0); ios_base::sync_with_stdio(0);

    tree[0].sz = -1;
    string s;
    cin >> s;
    int n = SZ(s);

    id[0] = N++;
    tree[0].ch[s[0]-'a'] = id[0];
    tree[id[0]].sz=1;
    dp[id[0]]++;
    g[0].pb(id[0]);

    for(int i=1, v; i<n; i++) {
        v = id[i-1];
        while(v) {
            if(tree[v].sz<i && s[i-tree[v].sz-1]==s[i]) break;
            v = tree[v].suflnk;
        }
        if(v) {
            id[i] = (tree[v].ch[s[i]-'a']==-1 ? N++ : tree[v].ch[s[i]-'a']);
            tree[v].ch[s[i]-'a'] = id[i];
            tree[id[i]].sz = tree[v].sz+2;
            v = tree[v].suflnk;
            while(v) {
                if(s[i-tree[v].sz-1]==s[i]) break;
                v = tree[v].suflnk;
            }
            if(v) tree[id[i]].suflnk = tree[v].ch[s[i]-'a'];
            else if(s[i-1]==s[i] && tree[id[i]].sz>2) tree[id[i]].suflnk = tree[1].ch[s[i]-'a'];
            else tree[id[i]].suflnk = tree[0].ch[s[i]-'a'];
        }
        else if(s[i-1]==s[i]) {
            id[i] = (tree[1].ch[s[i]-'a']==-1 ? N++ : tree[1].ch[s[i]-'a']);
            tree[1].ch[s[i]-'a'] = id[i];
            tree[id[i]].sz = 2;
            tree[id[i]].suflnk = tree[0].ch[s[i]-'a'];
        }
        else {
            id[i] = (tree[0].ch[s[i]-'a']==-1 ? N++ : tree[0].ch[s[i]-'a']);
            tree[0].ch[s[i]-'a'] = id[i];
            tree[id[i]].sz = 1;
        }
        dp[id[i]]++;
        g[tree[id[i]].suflnk].pb(id[i]);
    }

    for(int i=0; i<N; i++) {
        sort(all(g[i]));
        g[i].resize(unique(all(g[i]))-g[i].begin());
    }

    dfs(0);

    int ans=0;
    for(int i=0; i<N; i++)
        maxs(ans, tree[i].sz*dp[i]);

    cout << ans << '\n';

    return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 0 / 26
• Subtask 5: 0 / 27