oj.uz

Submission #557406

# Submission time Handle Problem Language Result Execution time Memory
557406 2022-05-05T09:32:04 Z stefantaga Palindromes (APIO14_palindrome) C++14
100 / 100
 24 ms 36208 KB 
#include <bits/stdc++.h>

using namespace std;
string s;
struct PalTree
{
    int urm[27];
    int sufflink;
    int lung;
    int num;
}V[300005];
int suff,num;
void InitPalTree()
{
    num=2;
    suff=2;
    V[1].lung=-1;V[1].sufflink=1;
    V[2].lung=0; V[2].sufflink=1;
}
void adauga(int poz)
{
    int curr = suff;
    int letter = s[poz]-'a';
    while (true)
    {
        int lung = V[curr].lung;
        if (poz-lung-1>=0&&s[poz-lung-1]==s[poz])
        {
            break;
        }
        curr=V[curr].sufflink;
    }
    if (V[curr].urm[letter])
    {
        suff=V[curr].urm[letter];
        V[suff].num++;
        return;
    }
    num++;
    suff=num;
    V[curr].urm[letter]=num;
    V[num].lung=V[curr].lung+2;
    V[num].num=1;
    if (V[num].lung==1)
    {
        V[num].sufflink=2;
        return;
    }
    while (true)
    {
        curr=V[curr].sufflink;
        int lung = V[curr].lung;
        if (poz-lung-1>=0&&s[poz-lung-1]==s[poz])
        {
            V[num].sufflink=V[curr].urm[letter];
            break;
        }
    }
    return;
}
int i;
long long rasp;
int main()
{
    ios_base :: sync_with_stdio(false);
    cin.tie(0);
    #ifdef HOME
    ifstream cin("date.in");
    ofstream cout("date.out");
    #endif // HOME
    cin>>s;
    InitPalTree();
    for (i=0;i<s.size();i++)
    {
        adauga(i);
    }
    for (i=num;i>=3;i--)
    {
        rasp=max(rasp,1LL*V[i].num*V[i].lung);
        V[V[i].sufflink].num+=V[i].num;
    }
    cout<<rasp;
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:73:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   73 |     for (i=0;i<s.size();i++)
      |              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 212 KB Output is correct
2 Correct 0 ms 212 KB Output is correct
3 Correct 0 ms 212 KB Output is correct
4 Correct 0 ms 212 KB Output is correct
5 Correct 0 ms 212 KB Output is correct
6 Correct 1 ms 212 KB Output is correct
7 Correct 0 ms 212 KB Output is correct
8 Correct 0 ms 212 KB Output is correct
9 Correct 1 ms 212 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 1 ms 212 KB Output is correct
13 Correct 1 ms 336 KB Output is correct
14 Correct 1 ms 212 KB Output is correct
15 Correct 1 ms 212 KB Output is correct
16 Correct 1 ms 212 KB Output is correct
17 Correct 1 ms 212 KB Output is correct
18 Correct 1 ms 212 KB Output is correct
19 Correct 1 ms 324 KB Output is correct
20 Correct 1 ms 332 KB Output is correct
21 Correct 1 ms 340 KB Output is correct
22 Correct 1 ms 212 KB Output is correct
23 Correct 1 ms 212 KB Output is correct
24 Correct 1 ms 212 KB Output is correct
25 Correct 1 ms 212 KB Output is correct
26 Correct 1 ms 324 KB Output is correct
27 Correct 1 ms 212 KB Output is correct
28 Correct 1 ms 340 KB Output is correct
29 Correct 1 ms 212 KB Output is correct
30 Correct 1 ms 212 KB Output is correct
31 Correct 1 ms 212 KB Output is correct
32 Correct 1 ms 212 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 340 KB Output is correct
2 Correct 1 ms 340 KB Output is correct
3 Correct 0 ms 340 KB Output is correct
4 Correct 1 ms 340 KB Output is correct
5 Correct 1 ms 340 KB Output is correct
6 Correct 0 ms 340 KB Output is correct
7 Correct 0 ms 340 KB Output is correct
8 Correct 0 ms 340 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 212 KB Output is correct
11 Correct 1 ms 340 KB Output is correct
12 Correct 1 ms 340 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1492 KB Output is correct
2 Correct 1 ms 1492 KB Output is correct
3 Correct 1 ms 1492 KB Output is correct
4 Correct 1 ms 1492 KB Output is correct
5 Correct 1 ms 1492 KB Output is correct
6 Correct 1 ms 1492 KB Output is correct
7 Correct 1 ms 1488 KB Output is correct
8 Correct 1 ms 336 KB Output is correct
9 Correct 1 ms 340 KB Output is correct
10 Correct 1 ms 1108 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12244 KB Output is correct
2 Correct 7 ms 12244 KB Output is correct
3 Correct 6 ms 12244 KB Output is correct
4 Correct 8 ms 12244 KB Output is correct
5 Correct 8 ms 12272 KB Output is correct
6 Correct 6 ms 9044 KB Output is correct
7 Correct 7 ms 10452 KB Output is correct
8 Correct 3 ms 724 KB Output is correct
9 Correct 4 ms 3376 KB Output is correct
10 Correct 7 ms 10580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 35932 KB Output is correct
2 Correct 20 ms 35940 KB Output is correct
3 Correct 20 ms 36208 KB Output is correct
4 Correct 22 ms 36176 KB Output is correct
5 Correct 21 ms 36184 KB Output is correct
6 Correct 20 ms 32220 KB Output is correct
7 Correct 23 ms 30252 KB Output is correct
8 Correct 6 ms 1244 KB Output is correct
9 Correct 6 ms 1244 KB Output is correct
10 Correct 20 ms 29784 KB Output is correct
11 Correct 24 ms 36144 KB Output is correct
12 Correct 7 ms 4308 KB Output is correct