oj.uz

Submission #331149

# Submission time Handle Problem Language Result Execution time Memory
331149 2020-11-27T14:29:14 Z couplefire Palindromes (APIO14_palindrome) C++17
100 / 100
 59 ms 40552 KB 
#include <bits/stdc++.h>
using namespace std;
#define MAXN 300005

template<int SZ> struct PalTree{
    static const int sigma = 26;
    int s[SZ], len[SZ], link[SZ], to[SZ][sigma], oc[SZ];
    int n, last, sz;
    PalTree(){
        s[n++] = -1;
        link[0] = 1;
        len[1] = -1;
        sz = 2;
    }
    int getLink(int v){
        while(s[n-len[v]-2] != s[n-1]) v = link[v];
        return v;
    }
    void add(int c){
        s[n++] = c;
        last = getLink(last);
        if(!to[last][c]){
            len[sz] = len[last]+2;
            link[sz] = to[getLink(link[last])][c];
            to[last][c] = sz++;
        }
        last = to[last][c];
        oc[last]++;
    }
    void prop(){
        vector<pair<int, int>> v;
        for(int i = 2; i<sz; i++) v.push_back({len[i], i});
        sort(v.begin(), v.end()); reverse(v.begin(), v.end());
        for(auto a : v) oc[link[a.second]] += oc[a.second];
    }
};

PalTree<MAXN> tree;
string s;

int main(){
    // freopen("a.in", "r", stdin);
    ios_base::sync_with_stdio(false);
    cin.tie(0);
    cin >> s;
    for(int i = 0; i<s.length(); i++){
        tree.add(s[i]-'a');
    }
    tree.prop();
    long long ans = 0;
    for(int i = 2; i<tree.sz; i++){
        ans = max(ans, 1ll*tree.len[i]*tree.oc[i]);
    }
    cout << ans << endl;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:46:21: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   46 |     for(int i = 0; i<s.length(); i++){
      |                    ~^~~~~~~~~~~
palindrome.cpp: In constructor 'PalTree<SZ>::PalTree() [with int SZ = 300005]':
palindrome.cpp:10:11: warning: '*<unknown>.PalTree<300005>::n' is used uninitialized in this function [-Wuninitialized]
   10 |         s[n++] = -1;
      |           ^

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 1772 KB Output is correct
2 Correct 2 ms 1772 KB Output is correct
3 Correct 2 ms 1772 KB Output is correct
4 Correct 2 ms 1772 KB Output is correct
5 Correct 2 ms 1772 KB Output is correct
6 Correct 3 ms 1772 KB Output is correct
7 Correct 3 ms 1772 KB Output is correct
8 Correct 1 ms 492 KB Output is correct
9 Correct 1 ms 492 KB Output is correct
10 Correct 2 ms 1388 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 13 ms 13608 KB Output is correct
2 Correct 20 ms 13608 KB Output is correct
3 Correct 18 ms 13608 KB Output is correct
4 Correct 19 ms 13608 KB Output is correct
5 Correct 20 ms 13608 KB Output is correct
6 Correct 14 ms 10536 KB Output is correct
7 Correct 17 ms 11944 KB Output is correct
8 Correct 3 ms 1132 KB Output is correct
9 Correct 5 ms 4076 KB Output is correct
10 Correct 18 ms 11816 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 49 ms 40552 KB Output is correct
2 Correct 57 ms 40552 KB Output is correct
3 Correct 41 ms 40552 KB Output is correct
4 Correct 59 ms 40552 KB Output is correct
5 Correct 57 ms 40552 KB Output is correct
6 Correct 52 ms 36712 KB Output is correct
7 Correct 48 ms 32768 KB Output is correct
8 Correct 6 ms 2420 KB Output is correct
9 Correct 6 ms 2420 KB Output is correct
10 Correct 46 ms 32376 KB Output is correct
11 Correct 42 ms 40552 KB Output is correct
12 Correct 9 ms 5876 KB Output is correct