Submission #552168

#	Time	Username	Problem	Language	Result	Execution time	Memory
552168		tht2005	Palindromes (APIO14_palindrome)	C++17	100 / 100	45 ms	51356 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;

const int N = 300005;
int n;
long long res;
char s[N];
int nNode, edge[N][26], link[N], len[N], f[N];
vector<int> aj[N];

int main() {
    scanf("%s", s);
    n = strlen(s);
    len[0] = -1; link[0] = 0;
    len[1] = 0; link[1] = 0;
    nNode = 2;
    memset(edge, 0xff, sizeof(edge));
    for(int i = 0, cur = 0; i < n; ++i) {
        int c = s[i] - 'a', p = cur;
        while(s[i - 1 - len[p]] != s[i]) p = link[p];
        if(edge[p][c] == -1) {
            edge[p][c] = nNode;
            len[nNode] = len[p] + 2;
            int q = link[p];
            while(s[i - 1 - len[q]] != s[i]) q = link[q];
            if(p)
                link[nNode] = edge[q][c];
            else
                link[nNode] = 1;
            ++nNode;
        }
        cur = edge[p][c];
        ++f[cur];
    }
    res = 0;
    for(int i = nNode; i--; ) {
        aj[link[i]].push_back(i);
        for(int j : aj[i]) {
            f[i] += f[j];
        }
        res = max(res, (long long)len[i] * f[i]);
    }
    printf("%lld", res);
    return 0;
}

Compilation message (stderr)

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

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