oj.uz

Submission #140065

# Submission time Handle Problem Language Result Execution time Memory
140065 2019-08-02T01:35:23 Z shamimjucse Palindromes (APIO14_palindrome) C++14
100 / 100
 70 ms 36408 KB 
#include<bits/stdc++.h>
#define ll long long
using namespace std;

const int mx = 300005;
int tr[mx][26], node;
int len[mx], link[mx],suff;
string s; /// 1-indexed
int cnt[mx],occ[mx];
inline void Insert(int p)
{
    while(s[p - len[suff] - 1] != s[p])
        suff = link[suff];
    int x = link[suff], c = s[p] - 'a';
    while(s[p - len[x] - 1] != s[p])
        x = link[x];
    if(!tr[suff][c])
    {
        tr[suff][c] = ++node;
        len[node] = len[suff] + 2;
        link[node] = (len[node] == 1) ? 2 : tr[x][c];
        cnt[node]+=1 + cnt[link[node]];
    }
    suff = tr[suff][c];
    occ[suff]++;
}
void initTree()
{
    node = 2, suff = 2;
    len[1] = -1, link[1] = 1;
    len[2] = 0, link[2] = 1;
}
ll totalpalindreme = 0;
void buildTree()
{
    initTree();
    s = "#" + s;
    for(int i=1;i<s.size();i++)
    {
        Insert(i);
        totalpalindreme+=cnt[suff];
    }
}
ll countPalindromes()
{
    ll sum = 0;
    for(int i=node;i>2;i--)
    {
        occ[link[i]]+=occ[i];
        sum = max(sum,1LL*occ[i]*len[i]);
    }
    return sum;
}
int main()
{
    cin >> s;
    buildTree();
    //cout << totalpalindreme << endl;
    cout << countPalindromes() << endl;
    return 0;
}

Compilation message

palindrome.cpp: In function 'void buildTree()':
palindrome.cpp:38:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for(int i=1;i<s.size();i++)
                 ~^~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 1656 KB Output is correct
2 Correct 4 ms 1528 KB Output is correct
3 Correct 4 ms 1528 KB Output is correct
4 Correct 4 ms 1528 KB Output is correct
5 Correct 4 ms 1528 KB Output is correct
6 Correct 4 ms 1528 KB Output is correct
7 Correct 4 ms 1528 KB Output is correct
8 Correct 3 ms 376 KB Output is correct
9 Correct 3 ms 376 KB Output is correct
10 Correct 4 ms 1144 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 22 ms 12276 KB Output is correct
2 Correct 22 ms 12276 KB Output is correct
3 Correct 23 ms 12376 KB Output is correct
4 Correct 23 ms 12404 KB Output is correct
5 Correct 24 ms 12276 KB Output is correct
6 Correct 20 ms 9048 KB Output is correct
7 Correct 21 ms 10484 KB Output is correct
8 Correct 10 ms 628 KB Output is correct
9 Correct 13 ms 3444 KB Output is correct
10 Correct 21 ms 10612 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 63 ms 36012 KB Output is correct
2 Correct 63 ms 35948 KB Output is correct
3 Correct 64 ms 35940 KB Output is correct
4 Correct 65 ms 35944 KB Output is correct
5 Correct 70 ms 35944 KB Output is correct
6 Correct 59 ms 32108 KB Output is correct
7 Correct 58 ms 30056 KB Output is correct
8 Correct 25 ms 1044 KB Output is correct
9 Correct 25 ms 1304 KB Output is correct
10 Correct 61 ms 29824 KB Output is correct
11 Correct 63 ms 36408 KB Output is correct
12 Correct 29 ms 4460 KB Output is correct