oj.uz

Submission #171922

# Submission time Handle Problem Language Result Execution time Memory
171922 2019-12-30T15:53:34 Z Ruxandra985 Palindromes (APIO14_palindrome) C++14
100 / 100
 140 ms 67548 KB 
#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

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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42616 KB Output is correct
2 Correct 41 ms 42616 KB Output is correct
3 Correct 40 ms 42616 KB Output is correct
4 Correct 41 ms 42616 KB Output is correct
5 Correct 42 ms 42744 KB Output is correct
6 Correct 41 ms 42616 KB Output is correct
7 Correct 40 ms 42620 KB Output is correct
8 Correct 41 ms 42616 KB Output is correct
9 Correct 48 ms 42616 KB Output is correct
10 Correct 48 ms 42616 KB Output is correct
11 Correct 40 ms 42616 KB Output is correct
12 Correct 41 ms 42616 KB Output is correct
13 Correct 41 ms 42616 KB Output is correct
14 Correct 41 ms 42616 KB Output is correct
15 Correct 63 ms 42560 KB Output is correct
16 Correct 47 ms 42616 KB Output is correct
17 Correct 41 ms 42616 KB Output is correct
18 Correct 49 ms 42640 KB Output is correct
19 Correct 45 ms 42656 KB Output is correct
20 Correct 40 ms 42608 KB Output is correct
21 Correct 42 ms 42616 KB Output is correct
22 Correct 40 ms 42620 KB Output is correct
23 Correct 40 ms 42616 KB Output is correct
24 Correct 41 ms 42616 KB Output is correct
25 Correct 41 ms 42616 KB Output is correct
26 Correct 41 ms 42616 KB Output is correct
27 Correct 41 ms 42616 KB Output is correct
28 Correct 40 ms 42616 KB Output is correct
29 Correct 40 ms 42616 KB Output is correct
30 Correct 40 ms 42616 KB Output is correct
31 Correct 40 ms 42616 KB Output is correct
32 Correct 40 ms 42616 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 42700 KB Output is correct
2 Correct 41 ms 42620 KB Output is correct
3 Correct 40 ms 42744 KB Output is correct
4 Correct 40 ms 42744 KB Output is correct
5 Correct 41 ms 42616 KB Output is correct
6 Correct 41 ms 42872 KB Output is correct
7 Correct 41 ms 42756 KB Output is correct
8 Correct 41 ms 42716 KB Output is correct
9 Correct 41 ms 42616 KB Output is correct
10 Correct 41 ms 42616 KB Output is correct
11 Correct 41 ms 42616 KB Output is correct
12 Correct 41 ms 42616 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 43192 KB Output is correct
2 Correct 43 ms 43128 KB Output is correct
3 Correct 42 ms 43384 KB Output is correct
4 Correct 42 ms 43384 KB Output is correct
5 Correct 42 ms 42824 KB Output is correct
6 Correct 49 ms 42872 KB Output is correct
7 Correct 50 ms 43020 KB Output is correct
8 Correct 41 ms 42616 KB Output is correct
9 Correct 41 ms 42648 KB Output is correct
10 Correct 42 ms 42744 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 64 ms 48508 KB Output is correct
2 Correct 61 ms 47480 KB Output is correct
3 Correct 63 ms 50936 KB Output is correct
4 Correct 60 ms 49244 KB Output is correct
5 Correct 57 ms 44152 KB Output is correct
6 Correct 53 ms 45048 KB Output is correct
7 Correct 57 ms 46200 KB Output is correct
8 Correct 46 ms 43128 KB Output is correct
9 Correct 49 ms 44792 KB Output is correct
10 Correct 53 ms 44024 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 113 ms 60536 KB Output is correct
2 Correct 110 ms 55480 KB Output is correct
3 Correct 132 ms 67548 KB Output is correct
4 Correct 126 ms 58672 KB Output is correct
5 Correct 140 ms 48504 KB Output is correct
6 Correct 99 ms 54280 KB Output is correct
7 Correct 111 ms 52728 KB Output is correct
8 Correct 54 ms 44024 KB Output is correct
9 Correct 53 ms 44152 KB Output is correct
10 Correct 100 ms 47840 KB Output is correct
11 Correct 129 ms 55804 KB Output is correct
12 Correct 63 ms 46324 KB Output is correct