Submission #885042

#	Time	Username	Problem	Language	Result	Execution time	Memory
885042		patrikpavic2	Palindromes (APIO14_palindrome)	C++17	100 / 100	260 ms	81360 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() { len = 0, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch)); }
    node(int _len) { len = _len, cnt = 0, bk = 0, memset(ch, 0, sizeof(ch));  }
};
 
node *n0, *n1;
vector < node* > v;
 
node* create_eertree(string &s){
    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;
}
 
 
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