Submission #171922

#	Time	Username	Problem	Language	Result	Execution time	Memory
171922		Ruxandra985	Palindromes (APIO14_palindrome)	C++14	100 / 100	140 ms	67548 KiB

palindrome

#include <bits/stdc++.h>
#define DIMN 300010
using namespace std;
int s[DIMN];
struct eertree{
    int len , fq , sl; /// suffix link
    int v[26];
    vector <int> inv; /// suffix linkuri inverse
    eertree(){
        for (int i = 0 ; i < 26 ; i++)
            v[i] = -1;
    }
};
eertree t[DIMN];
int rsmall , rbig;
int nodes = 1;
long long sol;
void go_up (int &r , int poz){
    int aux;
    //if (poz == 4)
      //  printf ("a");
    //printf ("%d ", r);
    while (true){

        if (1 <= poz - t[r].len - 1 && s[poz - t[r].len - 1] == s[poz]){ /// AM GASIT
            break;
        }
        else r= t[r].sl; /// te duci sus

    }
    nodes++;
    if (t[r].v[s[poz]] == -1){
        t[r].v[s[poz]] = nodes;
        t[ nodes ].len = 2 + t[r].len;
    }
    t[ t[r].v[s[poz]] ].fq++;
    /// acum r e la adresa palindromului in jurul caruia pui s[poz]
    /// update last_suff_pal pt noul prefix 1..poz
    if (t[ t[r].v[s[poz]] ].fq != 1){ /// il aveai deja nu conteaza
        r = t[r].v[s[poz]];
        return;
    }
    if (t[nodes].len == 1){

        aux = 1;
        r = t[r].v[s[poz]];
        t[r].sl = aux;
        t[aux].inv.push_back(r);

        return;
    }
    aux = t[r].sl;
    /// la r adaugi suffix link
    while (true){

        if (1 <= poz - t[aux].len - 1 && s[poz - t[aux].len - 1] == s[poz]){ /// AM GASIT
            t[nodes].sl = t[aux].v[s[poz]];
            t[ t[aux].v[s[poz]] ].inv.push_back(nodes);
            break;
        }
        else aux= t[aux].sl; /// te duci sus

    }
    r = t[r].v[s[poz]];
}
int dfs (int r){
    int i , sum = t[r].fq , vecin;
    //printf ("%d ", r);
    for ( i=0 ; i < t[r].inv.size() ; i++){
        vecin = t[r].inv[i];
        sum = sum + dfs(vecin);
    }
    sol = max(sol , (long long)t[r].len * sum);

    //printf ("%d %d\n" ,t[r].len , sum);

    return sum;

}
int main()
{
    FILE *fin = stdin;
    FILE *fout = stdout;
    int n , i;
    int last_suff_pal;
    char c;
    c=fgetc(fin);
    n = 0;
    while ('a'<=c && c <='z'){
        s[++n] = c - 'a';
        c = fgetc(fin);
    }
    rsmall = 0;
    rbig = 1;
    t[rsmall].len = -1;
    t[rsmall].sl = rsmall;
    t[rbig].sl = rsmall;
    t[rsmall].inv.push_back(rbig);
    last_suff_pal = 1; /// momentan nu am
    for (i=1;i<=n;i++){
        /// pui litera i
        /// vreau sa gasesc last_suff_pal acum ca am extins
        go_up(last_suff_pal , i);
        /// am stabilit ca last suff pal e baza la care adaugam s[i]
    }

    sol = 0;
    dfs(rsmall); /// dfs doar din rsmall ca oricum ajung si in rbig
    fprintf (fout,"%lld",sol);
    return 0;
}

Compilation message (stderr)

palindrome.cpp: In function 'int dfs(int)':
palindrome.cpp:69:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( i=0 ; i < t[r].inv.size() ; i++){
                 ~~^~~~~~~~~~~~~~~~~

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