Submission #260635

#	Time	Username	Problem	Language	Result	Execution time	Memory
260635		shayan_p	Palindromes (APIO14_palindrome)	C++17	100 / 100	87 ms	65536 KiB

palindrome

// And you curse yourself for things you never done

#include<bits/stdc++.h>

#define F first
#define S second
#define PB push_back
#define sz(s) int((s).size())
#define bit(n,k) (((n)>>(k))&1)

using namespace std;

typedef long long ll;
typedef pair<int,int> pii;

const int maxn = 3e5 + 10, mod = 1e9 + 7, inf = 1e9 + 10;

int f[maxn], ln[maxn];
int nxt[maxn][26];
vector<int> v[maxn];

int val[maxn];

ll ANS;
int dfs(int u){
    int num = val[u];
    for(int y : v[u]){
	num+= dfs(y);
    }
    ANS = max(ANS, 1ll * num * ln[u]);
    return num;
}

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

    int C = 2;
    ln[0] = -1;
    ln[1] = 0;
    f[1] = 0;
    f[0] = 0;
    
    string s;
    cin >> s;
    int tmp = 1;
    for(int i = 0; i < sz(s); i++){
	while(i - ln[tmp] <= 0 || s[i - ln[tmp] - 1] != s[i])
	    tmp = f[tmp];
	if(nxt[tmp][s[i] - 'a'] == 0){
	    ln[C] = ln[tmp] + 2;
	    nxt[tmp][s[i] - 'a'] = C;

	    int tmp2 = f[tmp];
	    while(i - ln[tmp2] <= 0 || s[i - ln[tmp2] - 1] != s[i])
		tmp2 = f[tmp2];
	    if(tmp == 0)
		f[C] = 1;
	    else
		f[C] = nxt[tmp2][s[i] - 'a'];
	    C++;
	}	
	tmp = nxt[tmp][s[i] - 'a'];
	val[tmp]++;
    }
    for(int i = 1; i < C; i++){
	v[f[i]].PB(i);
    }    
    dfs(0);
    return cout << ANS << endl, 0;
}

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