Submission #171886

#	Time	Username	Problem	Language	Result	Execution time	Memory
171886		Ruxandra985	Palindromes (APIO14_palindrome)	C++14	0 / 100	115 ms	60536 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;
    while (true){
        if (r == rsmall){ /// e pe -1
            if (poz != 1 && s[poz] == s[poz-1]){
                r = rbig;
            }
            if (t[r].v[s[poz]] == -1){
                t[r].v[s[poz]] = ++nodes;
                t[ t[r].v[s[poz]] ].len = 2 + t[r].len;
            }
            t[ t[r].v[s[poz]] ].fq++;
            break;
        }
        else {
            if (1 <= poz - t[r].len - 1 && s[poz - t[r].len - 1] == s[poz]){ /// AM GASIT
                if (t[r].v[s[poz]] == -1){
                    t[r].v[s[poz]] = ++nodes;
                    t[ t[r].v[s[poz]] ].len = 2 + t[r].len;
                }
                t[ t[r].v[s[poz]] ].fq++;
                break;
            }
            else r= t[r].sl; /// te duci sus

        }
    }
    /// 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
        return;
    aux = t[r].sl;
    /// la r adaugi suffix link
    while (true){
        if (aux == rsmall){ /// e pe -1
            if (poz != 1 && s[poz] == s[poz-1] && r != rbig){
                aux = rbig;
            }
            if (aux == r){
                break;
            }
            if (t[aux].v[s[poz]] == -1){
                t[aux].v[s[poz]] = ++nodes;
                t[ t[aux].v[s[poz]] ].len = 2 + t[aux].len;
            }
            break;
        }
        else {
            if (1 <= poz - t[aux].len - 1 && s[poz - t[aux].len - 1] == s[poz]){ /// AM GASIT
                if (t[aux].v[s[poz]] == -1){
                    t[aux].v[s[poz]] = ++nodes;
                    t[ t[aux].v[s[poz]] ].len = 2 + t[aux].len;
                }
                break;
            }
            else aux= t[aux].sl; /// te duci sus

        }
    }
    if (aux!= rsmall || r != rsmall){
        r = t[r].v[s[poz]];
        t[r].sl = t[aux].v[s[poz]];
        t [ t[aux].v[s[poz]] ].inv.push_back(r);
    }
    else {
        r = t[r].v[s[poz]];
        t[r].sl = aux;
        t[aux].inv.push_back(r);
    }

}
int dfs (int r){
    int i , sum = t[r].fq , vecin;

    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);

    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);
    }

    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:92:19: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for ( i=0 ; i < t[r].inv.size() ; i++){
                 ~~^~~~~~~~~~~~~~~~~

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