oj.uz

Submission #493519

# Submission time Handle Problem Language Result Execution time Memory
493519 2021-12-11T20:17:36 Z JovanB Palindromes (APIO14_palindrome) C++17
100 / 100
 28 ms 36620 KB 
#include <bits/stdc++.h>
using namespace std;

using ll = long long;
using ld = long double;

ll res = 0;

const int C = 1000000;

struct PTree{
    struct Node{
        int len, cnt, slink, dpt, to[26];
    } tree[C];
    int suf = 0;
    int idxx = 0;
    string s = "";
    void init(){
        tree[1].len = -1, tree[1].cnt = 0, tree[1].slink = 1, tree[1].dpt = 0;
        tree[2].len = 0, tree[2].cnt = 0, tree[2].slink = 1, tree[1].dpt = 0;
        suf = idxx = 2;
    }
    void addChar(char c){
        s += c;
        int n = s.size();
        while(n - 2 - tree[suf].len < 0 || s[n - 2 - tree[suf].len] != c) suf = tree[suf].slink;
        int node = tree[suf].to[c - 'a'];
        if(node == 0){
            node = ++idxx;
            tree[suf].to[c - 'a'] = idxx;
            tree[node].len = tree[suf].len + 2;
            if(suf == 1) tree[node].slink = 2;
            else{
                int v = tree[suf].slink;
                while(s[n - 2 - tree[v].len] != c) v = tree[v].slink;
                tree[node].slink = tree[v].to[c - 'a'];
            }
            tree[node].dpt = tree[tree[node].slink].dpt + 1;
        }
        tree[node].cnt++;
        suf = node;
    }
    void calc(){
        for(int node=idxx; node>=3; node--){
            res = max(res, 1LL*tree[node].len*tree[node].cnt);
            tree[tree[node].slink].cnt += tree[node].cnt;
        }
    }
} pal;

int main(){
    ios_base::sync_with_stdio(false), cin.tie(0);
    cout.precision(10);
    cout << fixed;

    string s;
    cin >> s;
    pal.init();
    for(auto c : s) pal.addChar(c);
    pal.calc();
    cout << res << "\n";
    return 0;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1484 KB Output is correct
2 Correct 1 ms 1484 KB Output is correct
3 Correct 1 ms 1484 KB Output is correct
4 Correct 1 ms 1484 KB Output is correct
5 Correct 1 ms 1484 KB Output is correct
6 Correct 2 ms 1476 KB Output is correct
7 Correct 1 ms 1484 KB Output is correct
8 Correct 1 ms 332 KB Output is correct
9 Correct 1 ms 332 KB Output is correct
10 Correct 1 ms 1100 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 12492 KB Output is correct
2 Correct 9 ms 12492 KB Output is correct
3 Correct 8 ms 12492 KB Output is correct
4 Correct 8 ms 12492 KB Output is correct
5 Correct 10 ms 12416 KB Output is correct
6 Correct 7 ms 9292 KB Output is correct
7 Correct 8 ms 10700 KB Output is correct
8 Correct 3 ms 844 KB Output is correct
9 Correct 3 ms 3532 KB Output is correct
10 Correct 6 ms 10752 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 21 ms 36528 KB Output is correct
2 Correct 27 ms 36620 KB Output is correct
3 Correct 22 ms 36448 KB Output is correct
4 Correct 27 ms 36484 KB Output is correct
5 Correct 28 ms 36452 KB Output is correct
6 Correct 25 ms 32560 KB Output is correct
7 Correct 21 ms 30524 KB Output is correct
8 Correct 8 ms 1748 KB Output is correct
9 Correct 7 ms 1748 KB Output is correct
10 Correct 20 ms 30140 KB Output is correct
11 Correct 28 ms 36548 KB Output is correct
12 Correct 8 ms 4600 KB Output is correct