oj.uz

Submission #486178

# Submission time Handle Problem Language Result Execution time Memory
486178 2021-11-10T17:25:59 Z Turin Palindromes (APIO14_palindrome) C++14
100 / 100
 55 ms 112844 KB 
#include<bits/stdc++.h>
using namespace std;
using ll = long long;
using ii = pair<int,int>;

#define ff first
#define se second
#define pb push_back
#define all(x) (x).begin(),(x).end()

const int mod = 1e9 + 7;
const int inf = 1e9 + 9;
const int mx  = 1e6 + 5;

int tree[mx][26], idx;
char s[mx]; int ans[mx];
int len[mx], link[mx], t, occ[mx];

void init(){
    memset(ans, 0, sizeof ans);
    memset(occ, 0, sizeof occ);
    memset(tree, 0, sizeof tree);

    len[1] = -1; link[1] = 1;
    len[2] = 0;  link[2] = 1;
    idx = t = 2;
}

void extend(int p){
    while(s[p-len[t]-1] != s[p]) t=link[t];
    int x = link[t], c = s[p] - 'a';
    while(s[p-len[x]-1] != s[p]) x=link[x];
    if(!tree[t][c]){
        tree[t][c] = ++idx;
        len[idx] = len[t] + 2;
        link[idx] = len[idx] == 1 ? 2 : tree[x][c];
        ans[idx] = 1 + ans[link[idx]];
    }t = tree[t][c]; ++occ[t];
}

ll solve(){
    int n = strlen(s);
    for(int i=0; i<n; ++i) extend(i);
    for(int i=idx; i>2; --i)
        occ[link[i]] += occ[i];
    ll ans = 0;
    for(int i=2; i<=idx; ++i)
        ans = max(ans, 1LL*len[i]*occ[i]);
    return ans;
}

int main(){

    ios_base::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    int q = 1; // cin >> q;
    for(int cs=1; cs<=q; ++cs){
        cin >> s; init();
        cout << solve() << "\n";
    }

    return 0;
}

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 39 ms 109896 KB Output is correct
2 Correct 42 ms 109844 KB Output is correct
3 Correct 38 ms 109860 KB Output is correct
4 Correct 37 ms 109788 KB Output is correct
5 Correct 42 ms 109908 KB Output is correct
6 Correct 38 ms 109892 KB Output is correct
7 Correct 40 ms 109772 KB Output is correct
8 Correct 41 ms 109860 KB Output is correct
9 Correct 40 ms 109892 KB Output is correct
10 Correct 46 ms 109892 KB Output is correct
11 Correct 38 ms 109780 KB Output is correct
12 Correct 39 ms 109892 KB Output is correct
13 Correct 38 ms 109856 KB Output is correct
14 Correct 44 ms 109832 KB Output is correct
15 Correct 38 ms 109808 KB Output is correct
16 Correct 38 ms 109860 KB Output is correct
17 Correct 38 ms 109900 KB Output is correct
18 Correct 37 ms 109848 KB Output is correct
19 Correct 41 ms 109892 KB Output is correct
20 Correct 39 ms 109804 KB Output is correct
21 Correct 38 ms 109840 KB Output is correct
22 Correct 38 ms 109876 KB Output is correct
23 Correct 38 ms 109888 KB Output is correct
24 Correct 38 ms 109848 KB Output is correct
25 Correct 44 ms 109812 KB Output is correct
26 Correct 38 ms 109884 KB Output is correct
27 Correct 40 ms 109836 KB Output is correct
28 Correct 38 ms 109840 KB Output is correct
29 Correct 43 ms 109856 KB Output is correct
30 Correct 37 ms 109868 KB Output is correct
31 Correct 39 ms 109804 KB Output is correct
32 Correct 38 ms 109900 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 40 ms 109792 KB Output is correct
2 Correct 39 ms 109844 KB Output is correct
3 Correct 41 ms 109816 KB Output is correct
4 Correct 41 ms 109888 KB Output is correct
5 Correct 40 ms 109872 KB Output is correct
6 Correct 37 ms 109896 KB Output is correct
7 Correct 40 ms 109904 KB Output is correct
8 Correct 37 ms 109836 KB Output is correct
9 Correct 39 ms 109900 KB Output is correct
10 Correct 38 ms 109900 KB Output is correct
11 Correct 41 ms 109816 KB Output is correct
12 Correct 38 ms 109892 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 38 ms 109968 KB Output is correct
2 Correct 38 ms 109880 KB Output is correct
3 Correct 40 ms 109924 KB Output is correct
4 Correct 38 ms 109896 KB Output is correct
5 Correct 39 ms 110028 KB Output is correct
6 Correct 48 ms 109900 KB Output is correct
7 Correct 38 ms 109880 KB Output is correct
8 Correct 39 ms 109928 KB Output is correct
9 Correct 38 ms 109896 KB Output is correct
10 Correct 38 ms 109956 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 44 ms 110868 KB Output is correct
2 Correct 44 ms 110796 KB Output is correct
3 Correct 41 ms 110860 KB Output is correct
4 Correct 41 ms 110788 KB Output is correct
5 Correct 40 ms 110844 KB Output is correct
6 Correct 40 ms 110580 KB Output is correct
7 Correct 40 ms 110720 KB Output is correct
8 Correct 40 ms 110064 KB Output is correct
9 Correct 39 ms 110276 KB Output is correct
10 Correct 40 ms 110740 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 47 ms 112844 KB Output is correct
2 Correct 55 ms 112792 KB Output is correct
3 Correct 45 ms 112836 KB Output is correct
4 Correct 44 ms 112736 KB Output is correct
5 Correct 45 ms 112716 KB Output is correct
6 Correct 45 ms 112452 KB Output is correct
7 Correct 44 ms 112452 KB Output is correct
8 Correct 44 ms 110396 KB Output is correct
9 Correct 44 ms 110428 KB Output is correct
10 Correct 45 ms 112324 KB Output is correct
11 Correct 45 ms 112840 KB Output is correct
12 Correct 44 ms 110660 KB Output is correct