Submission #974564

#	Time	Username	Problem	Language	Result	Execution time	Memory
974564		flechita_veloz	Palindromes (APIO14_palindrome)	C++17	100 / 100	49 ms	71608 KiB

palindrome

#include<bits/stdc++.h>
#define all(x) x.begin(), x.end()
#define FORN(i,m,n) for(int i=(m); i<int(n); i++)
#define PRINTVEC(v) FORN(i,0,v.size()) cout<<v[i]<<" "; cout<<endl
#define PRINTMAT(m) FORN(j,0,m.size()) {PRINTVEC(m[j]);}
#define pb push_back
#define endl "\n"
#define sec second
#define fir first
#define print1(x) cout<<x<<endl;
#define print2(x,y) cout<<x<<": "<<y<<endl
using namespace std;

typedef long long ll; 
typedef pair<ll, ll> pll;
typedef pair<int, int> pii;
typedef vector<int> vi;
typedef vector<ll> vll;
typedef vector<vector<int> > vvi;
typedef vector<pii> vpi;
typedef vector<vll> vvll;

const int maxn = 3e5 + 5, sigma = 26; // sigma son las letras del abc
char s[maxn]; // aqui guardamos el string 
int len[maxn], link[maxn], to[maxn][sigma];
vvi edge(maxn);
vll ocurr(maxn);
int n = 0, last, sz;
// n es el tamanio acutal de la cadena, last el ultimo nodo al que accedimos
void init()
{
    s[n++] = -1; // cadena imaginaria
    link[0] = 1; // link suffix para palindromos pares
    len[1] = -1; // longitud de palindromo imaginario
    sz = 2; // tamanio actual del arbol, se comienza desde el nodo 3
    edge[0].pb(1);
}

// get_link encuentra un s[n - 1] X s[n - 1] sea un palindromo
// donde X es un palindromo
int get_link(int v)
{
    while(s[n - len[v] - 2] != s[n - 1]) v = link[v];
    return v;
}

void add_letter(int c)
{
    s[n++] = c; // agregamos una nueva letra
    last = get_link(last); // obtenemos el nuevo padre para nuestro nodo
    if(!to[last][c])
    {
        len [sz] = len[last] + 2; // actualizamos su len del nuevo nodo
        link[sz] = to[get_link(link[last])][c]; // obtemos su nuevo link del nodo
        edge[link[sz]].pb(sz);
        to[last][c] = sz++; // nueva arista al nuevo nodo 
    }
    last = to[last][c]; // actualizamos el ultimo nodo al q accedimos 
    ocurr[last]++;
}

ll ans = 0;
void dfs(int u = 0){
    for(auto v : edge[u]){
        dfs(v);
        ocurr[u] += ocurr[v];
    }
    ans = max(ans, ocurr[u] * len[u]);
}

int main(){
    ios_base::sync_with_stdio(false);
	cin.tie(0); cout.tie(0);
    init();
    char c;
    while((c = getchar()) != '\n'){
        add_letter(c - 'a');
    }
    dfs();
    cout << ans << endl;
    return 0;
}

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