oj.uz

Submission #734300

# Submission time Handle Problem Language Result Execution time Memory
734300 2023-05-02T09:09:27 Z bachhoangxuan Palindromes (APIO14_palindrome) C++17
100 / 100
 60 ms 69348 KB 
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int maxn=3e5+5;
struct node{
    int num=0,len,slink,nxt[26];
}tree[maxn];
int ans,lst,cnt=2;
string s;
void add(int p,int c){
    while(tree[lst].len==p || (s[p]!=s[p-tree[lst].len-1])) lst=tree[lst].slink;
    if(tree[lst].nxt[c]){
        lst=tree[lst].nxt[c];
        tree[lst].num++;
        return;
    }
    tree[lst].nxt[c]=++cnt;
    tree[cnt].len=tree[lst].len+2;
    tree[cnt].num++;
    if(tree[cnt].len==1){
        tree[cnt].slink=2;lst=cnt;
        return;
    }
    lst=tree[lst].slink;
    while(tree[lst].len==p || (s[p]!=s[p-tree[lst].len-1])) lst=tree[lst].slink;
    tree[cnt].slink=tree[lst].nxt[c];lst=cnt;
}
signed main(){
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);cout.tie(NULL);
    cin >> s;lst=2;
    tree[1].slink=tree[2].slink=1;
    tree[1].len=-1;tree[2].len=0;
    for(int i=0;i<(int)s.length();i++) add(i,s[i]-'a');
    for(int i=cnt;i>=2;i--){
        tree[tree[i].slink].num+=tree[i].num;
        ans=max(ans,tree[i].num*tree[i].len);
    }
    cout << ans << '\n';
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 25 ms 68308 KB Output is correct
2 Correct 29 ms 68388 KB Output is correct
3 Correct 27 ms 68308 KB Output is correct
4 Correct 26 ms 68368 KB Output is correct
5 Correct 27 ms 68428 KB Output is correct
6 Correct 26 ms 68416 KB Output is correct
7 Correct 26 ms 68308 KB Output is correct
8 Correct 31 ms 68300 KB Output is correct
9 Correct 26 ms 68308 KB Output is correct
10 Correct 26 ms 68340 KB Output is correct
11 Correct 26 ms 68332 KB Output is correct
12 Correct 25 ms 68384 KB Output is correct
13 Correct 29 ms 68416 KB Output is correct
14 Correct 25 ms 68392 KB Output is correct
15 Correct 30 ms 68396 KB Output is correct
16 Correct 27 ms 68308 KB Output is correct
17 Correct 27 ms 68324 KB Output is correct
18 Correct 26 ms 68348 KB Output is correct
19 Correct 26 ms 68308 KB Output is correct
20 Correct 26 ms 68376 KB Output is correct
21 Correct 26 ms 68376 KB Output is correct
22 Correct 26 ms 68296 KB Output is correct
23 Correct 27 ms 68404 KB Output is correct
24 Correct 27 ms 68320 KB Output is correct
25 Correct 34 ms 68320 KB Output is correct
26 Correct 29 ms 68304 KB Output is correct
27 Correct 30 ms 68404 KB Output is correct
28 Correct 26 ms 68324 KB Output is correct
29 Correct 26 ms 68332 KB Output is correct
30 Correct 26 ms 68300 KB Output is correct
31 Correct 26 ms 68308 KB Output is correct
32 Correct 29 ms 68408 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 68380 KB Output is correct
2 Correct 32 ms 68364 KB Output is correct
3 Correct 31 ms 68436 KB Output is correct
4 Correct 26 ms 68420 KB Output is correct
5 Correct 27 ms 68408 KB Output is correct
6 Correct 27 ms 68312 KB Output is correct
7 Correct 27 ms 68308 KB Output is correct
8 Correct 27 ms 68308 KB Output is correct
9 Correct 27 ms 68380 KB Output is correct
10 Correct 32 ms 68308 KB Output is correct
11 Correct 32 ms 68324 KB Output is correct
12 Correct 29 ms 68392 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 28 ms 68412 KB Output is correct
2 Correct 27 ms 68416 KB Output is correct
3 Correct 31 ms 68420 KB Output is correct
4 Correct 27 ms 68432 KB Output is correct
5 Correct 28 ms 68440 KB Output is correct
6 Correct 26 ms 68416 KB Output is correct
7 Correct 33 ms 68452 KB Output is correct
8 Correct 34 ms 68424 KB Output is correct
9 Correct 27 ms 68368 KB Output is correct
10 Correct 26 ms 68368 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 31 ms 68692 KB Output is correct
2 Correct 38 ms 68652 KB Output is correct
3 Correct 34 ms 68724 KB Output is correct
4 Correct 36 ms 68700 KB Output is correct
5 Correct 36 ms 68672 KB Output is correct
6 Correct 31 ms 68688 KB Output is correct
7 Correct 32 ms 68692 KB Output is correct
8 Correct 31 ms 68708 KB Output is correct
9 Correct 32 ms 68824 KB Output is correct
10 Correct 33 ms 68692 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 69348 KB Output is correct
2 Correct 60 ms 69344 KB Output is correct
3 Correct 44 ms 69328 KB Output is correct
4 Correct 48 ms 69320 KB Output is correct
5 Correct 54 ms 69340 KB Output is correct
6 Correct 47 ms 69244 KB Output is correct
7 Correct 47 ms 69268 KB Output is correct
8 Correct 34 ms 69300 KB Output is correct
9 Correct 36 ms 69300 KB Output is correct
10 Correct 42 ms 69316 KB Output is correct
11 Correct 48 ms 69328 KB Output is correct
12 Correct 36 ms 69320 KB Output is correct