oj.uz

Submission #825305

# Submission time Handle Problem Language Result Execution time Memory
825305 2023-08-14T17:11:59 Z taitruong270 Palindromes (APIO14_palindrome) C++17
100 / 100
 55 ms 79188 KB 
/*==============================================================================================================
         __                    __                                             _____     ______    _______
        |  |                  |  |                                           /  __ \   / _____|  / ______|     
      __|  |__              __|  |__                                         |_|  | |  | |       | |  
     |__|   __|            |__|   __|                                             | |  | |____   | |_____ 
        |  |    _____   _     |  |    ____  __  __  ____    _____    _____       / /   \ ___  \  |  ___  \
        |  |   /  _  \ | |    |  |   /  _/ | | | | /  _  \ /  __ \  /  _  \     / /         | |  | |   | |
        |  |_  | |_| | | |    |  |_  | |   | |_| | | |_| | | |  | | | |_| |    / /___   ____| |  | |___| |
        \____\ \____/| |_|    \____\ |_|   \_____/ \_____/ |_|  |_| \____ |   |______| |______/  \_______/
                                                                        | |
                                                                      __/ |
                                                                     |___/  
                                        Pratice, practice, and practice
                                       Where is the bug, delete it there
                                     Try, try, try again until you succeed
I hated every minute of training, but I said, 'Don't quit. Suffer now and live the rest of your life as a champion.' - Mohamed Ali 
                              You may not be the best, but must be the most effort
     Even the things and people you like, you don't have the courage to take, you are destined to be a failure.
                                           Difficult means more time
                                         Pain + Reflection = Progress 
==============================================================================================================*/
#include <bits/stdc++.h>
using namespace std;
#define ll long long
#define ld long double
#define endl '\n'
const ll mod = 1e9+7;
const ll inf = 1e18;

struct PalindromeTree
{
    struct node { ll len, num, link, nxt[30]; };
    vector<node> tree;
    string s;
    ll n, suff, maxn;

    PalindromeTree(){}
    PalindromeTree(string _s)
    {
        s=_s;
        tree.resize(s.size()+10);
        n=2;
        suff=2;
        tree[1]={-1, 0, 1};   //nut hu cau
        tree[2]={0, 0, 1};    //nut rong
        for (ll i=0; i<s.size(); i++) addLetter(i);
        pushNum();
    }

    bool addLetter(ll pos)
    {
        ll cur=suff, curlen=0, x=s[pos]-'a';
        //tim hau to A do dai lon nhat dang xAx bang lien ket hau to dai nhat
        cur=suff;
        while (true)
        {
            curlen=tree[cur].len;
            if (pos-1-curlen>=0 && s[pos]==s[pos-1-curlen]) break;
            cur=tree[cur].link;
        }

        if (tree[cur].nxt[x]!=0) //neu node da ton tai trong PalindromeTree thi ko can them 
        {
            tree[tree[cur].nxt[x]].num+=1;
            suff=tree[cur].nxt[x];
            return false;
        }

        suff=++n;           //them nut moi
        tree[n].len=tree[cur].len+2;
        tree[cur].nxt[x]=n;
        if (tree[n].len==1)
        {
            tree[n].link=2;
            tree[n].num+=1;
            return true;
        }
        // tim lien ket hau to dai nhat cua nut xAx la xBx
        cur=tree[cur].link;
        while (true)
        {
            curlen=tree[cur].len;
            if (pos-1-curlen>=0 && s[pos-1-curlen]==s[pos]) 
            {
                tree[n].link=tree[cur].nxt[x];
                break;
            }
            cur=tree[cur].link;
        }
        tree[n].num+=1;
        cur=n;
        return true;
    }

    void pushNum()
    {
        for (ll i=n; i>=3; i--) 
            tree[tree[i].link].num+=tree[i].num;
    }
};

void solve()
{
    string s; cin>>s;
    PalindromeTree pt(s);
    ll ans=0;
    for (ll i=3; i<=pt.n; i++) ans=max(ans, pt.tree[i].len*pt.tree[i].num);
    cout<<ans;
}

int main()
{
    ios_base::sync_with_stdio(false); cin.tie(NULL);
    clock_t start = clock();
    //#ifndef ONLINE_JUDGE
    //freopen("_input.txt", "r", stdin);
    //freopen("_output.txt", "w", stdout);
    //#endif
    solve();
    clock_t end = clock();
    cerr<<"Time: "<<fixed<<setprecision(10)<<double(end-start)/double(CLOCKS_PER_SEC)<<"\n";
    return 0;
}

Compilation message

palindrome.cpp: In constructor 'PalindromeTree::PalindromeTree(std::string)':
palindrome.cpp:46:23: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |         for (ll i=0; i<s.size(); i++) addLetter(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 1 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 0 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 0 ms 212 KB Output is correct
10 Correct 0 ms 212 KB Output is correct
11 Correct 0 ms 212 KB Output is correct
12 Correct 0 ms 212 KB Output is correct
13 Correct 0 ms 212 KB Output is correct
14 Correct 0 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 0 ms 212 KB Output is correct
18 Correct 0 ms 212 KB Output is correct
19 Correct 0 ms 340 KB Output is correct
20 Correct 0 ms 340 KB Output is correct
21 Correct 0 ms 340 KB Output is correct
22 Correct 0 ms 340 KB Output is correct
23 Correct 0 ms 340 KB Output is correct
24 Correct 0 ms 340 KB Output is correct
25 Correct 0 ms 340 KB Output is correct
26 Correct 1 ms 340 KB Output is correct
27 Correct 0 ms 340 KB Output is correct
28 Correct 0 ms 340 KB Output is correct
29 Correct 0 ms 340 KB Output is correct
30 Correct 1 ms 320 KB Output is correct
31 Correct 0 ms 340 KB Output is correct
32 Correct 0 ms 340 KB Output is correct

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 2900 KB Output is correct
2 Correct 2 ms 2852 KB Output is correct
3 Correct 2 ms 2900 KB Output is correct
4 Correct 2 ms 2864 KB Output is correct
5 Correct 2 ms 2900 KB Output is correct
6 Correct 2 ms 2928 KB Output is correct
7 Correct 1 ms 2900 KB Output is correct
8 Correct 1 ms 2900 KB Output is correct
9 Correct 2 ms 2888 KB Output is correct
10 Correct 2 ms 2900 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 26444 KB Output is correct
2 Correct 16 ms 26356 KB Output is correct
3 Correct 15 ms 26452 KB Output is correct
4 Correct 17 ms 26412 KB Output is correct
5 Correct 17 ms 26400 KB Output is correct
6 Correct 15 ms 26452 KB Output is correct
7 Correct 16 ms 26452 KB Output is correct
8 Correct 13 ms 26452 KB Output is correct
9 Correct 13 ms 26572 KB Output is correct
10 Correct 17 ms 26580 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 45 ms 78828 KB Output is correct
2 Correct 48 ms 78828 KB Output is correct
3 Correct 44 ms 78740 KB Output is correct
4 Correct 48 ms 78788 KB Output is correct
5 Correct 55 ms 78828 KB Output is correct
6 Correct 48 ms 78812 KB Output is correct
7 Correct 48 ms 78760 KB Output is correct
8 Correct 38 ms 78812 KB Output is correct
9 Correct 42 ms 79188 KB Output is correct
10 Correct 47 ms 79060 KB Output is correct
11 Correct 47 ms 79068 KB Output is correct
12 Correct 39 ms 79016 KB Output is correct