oj.uz

Submission #856498

# Submission time Handle Problem Language Result Execution time Memory
856498 2023-10-03T17:45:50 Z ttamx Palindromes (APIO14_palindrome) C++14
100 / 100
 49 ms 76232 KB 
#include<bits/stdc++.h>

using namespace std;

const int N=3e5+5;

struct node;
typedef node* pnode;
struct node{
    int len,cnt;
    pnode nxt[26],suf;
    node(int _len=1,int _cnt=1){
        len=_len;
        cnt=_cnt;
        for(int i=0;i<26;i++)nxt[i]=nullptr;
        suf=nullptr;
    }
};

int n;
string s;
int a[N];
vector<pnode> v;
pnode cur;
queue<pnode> q;
long long ans=0;

int main(){
    cin.tie(nullptr)->sync_with_stdio(false);
    cin >> s;
    n=s.size();
    a[0]=-1;
    for(int i=1;i<=n;i++)a[i]=s[i-1]-'a';
    v.emplace_back(new node(-1,0));
    v[0]->suf=v[0];
    v.emplace_back(new node(0,0));
    v[1]->suf=v[0];
    cur=v[0];
    for(int i=1;i<=n;i++){
        while(a[i]!=a[i-cur->len-1])cur=cur->suf;
        if(cur->nxt[a[i]]){
            cur=cur->nxt[a[i]];
            cur->cnt++;
            continue;
        }
        pnode tmp=cur->suf;
        cur=cur->nxt[a[i]]=new node(cur->len+2);
        v.emplace_back(cur);
        if(cur->len==1){
            cur->suf=v[1];
            continue;
        }
        while(a[i]!=a[i-tmp->len-1])tmp=tmp->suf;
        cur->suf=tmp->nxt[a[i]];
    }
    reverse(v.begin(),v.end());
    for(auto t:v){
        t->suf->cnt+=t->cnt;
        ans=max(ans,1ll*t->len*t->cnt);
    }
    cout << ans;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2908 KB Output is correct
2 Correct 1 ms 2908 KB Output is correct
3 Correct 1 ms 2908 KB Output is correct
4 Correct 2 ms 2908 KB Output is correct
5 Correct 2 ms 2908 KB Output is correct
6 Correct 1 ms 2908 KB Output is correct
7 Correct 1 ms 2776 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 0 ms 604 KB Output is correct
10 Correct 1 ms 2140 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 25040 KB Output is correct
2 Correct 14 ms 25084 KB Output is correct
3 Correct 13 ms 25228 KB Output is correct
4 Correct 15 ms 25112 KB Output is correct
5 Correct 15 ms 25036 KB Output is correct
6 Correct 11 ms 18640 KB Output is correct
7 Correct 12 ms 21456 KB Output is correct
8 Correct 2 ms 1112 KB Output is correct
9 Correct 4 ms 6596 KB Output is correct
10 Correct 11 ms 21456 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 75908 KB Output is correct
2 Correct 45 ms 76232 KB Output is correct
3 Correct 41 ms 75216 KB Output is correct
4 Correct 43 ms 74964 KB Output is correct
5 Correct 49 ms 74956 KB Output is correct
6 Correct 37 ms 68308 KB Output is correct
7 Correct 35 ms 62576 KB Output is correct
8 Correct 4 ms 2532 KB Output is correct
9 Correct 4 ms 2532 KB Output is correct
10 Correct 35 ms 61648 KB Output is correct
11 Correct 40 ms 74944 KB Output is correct
12 Correct 7 ms 9188 KB Output is correct