Submission #222227

#	Time	Username	Problem	Language	Result	Execution time	Memory
222227		Bruteforceman	Palindromes (APIO14_palindrome)	C++11	100 / 100	92 ms	66680 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
char s[300010];
int n;
struct data {
    int link, len, cnt;
    int nxt[26];
    data () {
        link = len = cnt = 0;
        memset(nxt, 0, sizeof nxt);
    }
} a[300010];
int last;
int node;
vector <int> g[300010];
int sub[300010];
long long opt;

void dfs(int x) {
    sub[x] = a[x].cnt;
    for(auto i : g[x]) {
        dfs(i);
        sub[x] += sub[i];
    }
    opt = max(opt, 1LL * sub[x] * a[x].len);
}
void addChar(int idx) {
    int c = s[idx] - 'a';
    int cur = last;
    while(true) {
        int len = a[cur].len;
        if(idx - len - 1 >= 0 && s[idx - len - 1] == s[idx]) {
            break;
        }
        cur = a[cur].link;
    }
    if(a[cur].nxt[c] != 0) {
        last = a[cur].nxt[c];
        a[last].cnt += 1;
        return ;
    }
    last = ++node;
    a[node].len = a[cur].len + 2;
    a[cur].nxt[c] = node;
    a[node].cnt += 1;
    if(a[node].len == 1) {
        a[node].link = 2;
        return ;
    }
    while(true) {
        cur = a[cur].link;
        int len = a[cur].len;
        if(idx - len - 1 >= 0 && s[idx - len - 1] == s[idx]) {
            a[node].link = a[cur].nxt[c];
            break;
        }
    }
    return ;
}
void initTree() {
    node = 2; last = 2;
    a[1].len = -1; a[2].len = 0;
    a[1].link = 1; a[2].link = 1;
}
int main() {
    scanf("%s", s);
    n = strlen(s);
    initTree();
    for(int i = 0; i < n; i++) {
        addChar(i);
    }
    for(int i = 2; i <= node; i++) {
        g[a[i].link].push_back(i);
    }
    dfs(1);
    printf("%lld\n", opt);
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:66:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%s", s);
     ~~~~~^~~~~~~~~

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