Submission #99956

#	Time	Username	Problem	Language	Result	Execution time	Memory
99956		Ramprosad	Palindromes (APIO14_palindrome)	C++14	100 / 100	66 ms	35220 KiB

palindrome

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

#define ll             long long
#define LL             long long
#define gcd(a,b)       __gcd(a, b)
#define lcm(a,b)       a * (b / gcd(a, b))
#define pii            pair<int, int>
#define pll            pair<ll, ll>
#define pil            pair<int, ll>
#define pli            pair<ll, int>
#define vi             vector<int>
#define vl             vector<ll>
#define vii            vector<pii>
#define vll            vector<pll>
#define vil            vector<pil>
#define vli            vector<pli>
#define pb             push_back
#define ppb            pop_back
#define mp             make_pair
#define ff             first
#define ss             second
#define all(v)         v.begin(), v.end()
#define fill(a, b)     memset(a, b, sizeof a)
#define smax(a, b)     a = max(a, b)
#define smin(a, b)     a = min(a, b)
#define sqr(x)         x * x
#define cube(x)        x * x * x
#define endl           '\n'

int in() {
    int n;
    scanf("%d", &n);
    return n;
}

ll Lin() {
    ll n;
    scanf("%lld", &n);
    return n;
}

double Din() {
    double n;
    scanf("%lf", &n);
    return n;
}

const ll inf = (ll)1e17;
const ll mod = (ll)1e9 + 7;
const int N = 3e5 + 5;

int tree[N][26], len[N], link[N], occ[N], node, t;

string s;

void add(int p){
    while(p - len[t] - 1 < 0 || s[p - len[t] - 1] != s[p]) t = link[t];
    int x = link[t], c = s[p] - 'a';
    while(p - len[x] - 1 < 0 || s[p - len[x] - 1] != s[p]) x = link[x];
    if(!tree[t][c]) {
        tree[t][c] = ++node;
        len[node] = len[t] + 2;
        link[node] = len[node] == 1 ? 2 : tree[x][c];
    }
    t = tree[t][c];
}

void buildPT() {
    len[1] = -1, len[2] = 0;
    link[1] = link[2] = 1;
    node = t = 2;
    int n = s.size();
    for(int i = 0; i < n; i++){
        add(i);
        occ[t]++;
    }
    ll ans = 0LL;
    for(int i = node; i > 2; i--){
        occ[link[i]] += occ[i];
        smax(ans, (ll)occ[i] * len[i]);
    }
    printf("%lld\n", ans);
}

int solve() {
    cin >> s;
    buildPT();
    return 0;
}

int main() {
    int test = 1, tc = 0;
    while(test--) {
        //printf("Case %d:\n", ++tc);
        solve();
    }
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int main()':
palindrome.cpp:93:19: warning: unused variable 'tc' [-Wunused-variable]
     int test = 1, tc = 0;
                   ^~
palindrome.cpp: In function 'int in()':
palindrome.cpp:33:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%d", &n);
     ~~~~~^~~~~~~~~~
palindrome.cpp: In function 'long long int Lin()':
palindrome.cpp:39:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lld", &n);
     ~~~~~^~~~~~~~~~~~
palindrome.cpp: In function 'double Din()':
palindrome.cpp:45:10: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
     scanf("%lf", &n);
     ~~~~~^~~~~~~~~~~

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