oj.uz

Submission #171886

# Submission time Handle Problem Language Result Execution time Memory
171886 2019-12-30T14:56:20 Z Ruxandra985 Palindromes (APIO14_palindrome) C++14
0 / 100
 115 ms 60536 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;
    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

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

# Verdict Execution time Memory Grader output
1 Correct 42 ms 42616 KB Output is correct
2 Correct 42 ms 42616 KB Output is correct
3 Correct 41 ms 42616 KB Output is correct
4 Correct 41 ms 42616 KB Output is correct
5 Correct 41 ms 42524 KB Output is correct
6 Correct 41 ms 42616 KB Output is correct
7 Correct 41 ms 42624 KB Output is correct
8 Correct 41 ms 42616 KB Output is correct
9 Correct 47 ms 42616 KB Output is correct
10 Correct 42 ms 42680 KB Output is correct
11 Correct 41 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 Incorrect 41 ms 42588 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 41 ms 42716 KB Output is correct
2 Correct 73 ms 42620 KB Output is correct
3 Correct 41 ms 42728 KB Output is correct
4 Correct 41 ms 42620 KB Output is correct
5 Correct 42 ms 42732 KB Output is correct
6 Correct 42 ms 42716 KB Output is correct
7 Correct 41 ms 42616 KB Output is correct
8 Correct 41 ms 42616 KB Output is correct
9 Correct 41 ms 42616 KB Output is correct
10 Correct 41 ms 42616 KB Output is correct
11 Correct 40 ms 42616 KB Output is correct
12 Incorrect 41 ms 42616 KB Output isn't correct

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 42 ms 43132 KB Output is correct
2 Correct 43 ms 43128 KB Output is correct
3 Correct 42 ms 43428 KB Output is correct
4 Correct 43 ms 43384 KB Output is correct
5 Correct 43 ms 42744 KB Output is correct
6 Correct 43 ms 42872 KB Output is correct
7 Correct 42 ms 43000 KB Output is correct
8 Correct 41 ms 42620 KB Output is correct
9 Correct 41 ms 42588 KB Output is correct
10 Incorrect 41 ms 42616 KB Output isn't correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 62 ms 48552 KB Output is correct
2 Correct 59 ms 47480 KB Output is correct
3 Correct 61 ms 50880 KB Output is correct
4 Correct 68 ms 49240 KB Output is correct
5 Correct 58 ms 44280 KB Output is correct
6 Correct 52 ms 44920 KB Output is correct
7 Correct 55 ms 46200 KB Output is correct
8 Correct 43 ms 43128 KB Output is correct
9 Incorrect 43 ms 43128 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 115 ms 60536 KB Output is correct
2 Incorrect 84 ms 52052 KB Output isn't correct
3 Halted 0 ms 0 KB -