oj.uz

Submission #251390

# Submission time Handle Problem Language Result Execution time Memory
251390 2020-07-21T05:32:07 Z phuleethanh Palindromes (APIO14_palindrome) C++14
100 / 100
 39 ms 35080 KB 
#include <bits/stdc++.h>
using namespace std;
const int N = 303030;
int last, num, child[N][26], len[N], suffLink[N], occ[N];
string s;

void insert(int i)
{
    while (s[i - len[last] - 1] != s[i])
        last = suffLink[last];
    int w = s[i] - 'a', temp = suffLink[last];
    while (s[i - len[temp] - 1] != s[i])
        temp = suffLink[temp];
    if (child[last][w] == 0)
    {
        child[last][w] = ++num, len[num] = len[last] + 2;
        suffLink[num] = (len[num] == 1 ? 0 : child[temp][w]);
    }
    last = child[last][w], ++occ[last];
}

int main()
{
    //freopen("z.inp", "r", stdin);
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    len[0] = 0, len[1] = -1, last = num = 1, suffLink[0] = suffLink[1] = 1;
    cin >> s;
    for (int i = 0; i < s.size(); i++)
        insert(i);
    long long ans = 0;
    for (int i = num; i > 1; i--)
    {
        ans = max(ans, 1ll * len[i] * occ[i]);
        occ[suffLink[i]] += occ[i]; //cap nhat nguoc len cho cac nut suffLink
    }
    cout << ans;
    return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:28:23: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
     for (int i = 0; i < s.size(); i++)
                     ~~^~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1536 KB Output is correct
2 Correct 1 ms 1536 KB Output is correct
3 Correct 2 ms 1536 KB Output is correct
4 Correct 3 ms 1536 KB Output is correct
5 Correct 1 ms 1536 KB Output is correct
6 Correct 1 ms 1536 KB Output is correct
7 Correct 2 ms 1536 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 1152 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 11904 KB Output is correct
2 Correct 10 ms 12032 KB Output is correct
3 Correct 9 ms 12032 KB Output is correct
4 Correct 10 ms 12032 KB Output is correct
5 Correct 9 ms 12032 KB Output is correct
6 Correct 7 ms 8960 KB Output is correct
7 Correct 8 ms 10240 KB Output is correct
8 Correct 3 ms 768 KB Output is correct
9 Correct 4 ms 3328 KB Output is correct
10 Correct 9 ms 10240 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 34824 KB Output is correct
2 Correct 26 ms 35080 KB Output is correct
3 Correct 37 ms 35072 KB Output is correct
4 Correct 38 ms 35072 KB Output is correct
5 Correct 26 ms 35080 KB Output is correct
6 Correct 25 ms 31360 KB Output is correct
7 Correct 23 ms 29448 KB Output is correct
8 Correct 7 ms 1288 KB Output is correct
9 Correct 7 ms 1288 KB Output is correct
10 Correct 23 ms 28928 KB Output is correct
11 Correct 39 ms 35072 KB Output is correct
12 Correct 9 ms 4360 KB Output is correct