Submission #885049

#	Time	Username	Problem	Language	Result	Execution time	Memory
885049		patrikpavic2	Palindromes (APIO14_palindrome)	C++17	100 / 100	247 ms	81096 KiB

palindrome

#include <algorithm>
#include <vector>
#include <cstdio>
#include <cstring>
#include <iostream>
 
#define PB push_back
 
using namespace std;
 
typedef long long ll;
 
const int N = 3e5 + 500;
const int INF = 0x3f3f3f3f;
const int ALP = 26;
 
struct node{
    node *ch[ALP], *bk;
    int len, cnt;
    node(int _len = 0) { 
    	len = _len, cnt = 0, bk = 0;
    	memset(ch, 0, sizeof(ch));  
    }
};
 
node* create_eertree(string &s){
    node *n0 = new node(0), *n1 = new node(-1);
    n0->bk = n1; n1->bk = n1;
    node* cur = n0;
    for(int i = 0;i < (int)s.size();i++){
        for(;cur->len+1>i||s[i-cur->len-1]!=s[i];cur=cur->bk);
        node *rmb = cur->bk;
        if(!cur->ch[s[i]-'a'])
            cur->ch[s[i]-'a'] = new node(cur->len + 2);
        cur = cur->ch[s[i]-'a']; cur->cnt++;
        for(;rmb->len+1>i||s[i-rmb->len-1]!=s[i];rmb=rmb->bk);
        if(cur->len == 1) cur->bk = n0;
        else{
            if(!rmb->ch[s[i]-'a']) 
            	rmb->ch[s[i]-'a'] = new node(rmb->len + 2);
            cur->bk = rmb->ch[s[i]-'a'];
        }
    }
    return n0;
}

 
 
bool cmp(node* X, node* Y){
    return X->len > Y->len;
}
 
vector < node* > v;
 
string s;
 
void dfs(node* x) {
	if(!x) return;
	v.PB(x);
	for(int i = 0;i < 26;i++)
		if(x->ch[i]) dfs(x->ch[i]);
}
 
int main(){
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    ll mx = 0;
    node* root = create_eertree(s);
    dfs(root); dfs(root->bk);
    sort(v.begin(), v.end(), cmp);
    for(int i = 0;i < (int)v.size();i++){
        mx = max(mx, (ll)v[i]->len * v[i]->cnt);
        v[i]->bk->cnt += v[i]->cnt;
    }
    cout << mx << endl;
}

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