oj.uz

Submission #764268

# Submission time Handle Problem Language Result Execution time Memory
764268 2023-06-23T09:48:15 Z Ahmed57 Palindromes (APIO14_palindrome) C++17
47 / 100
 1000 ms 9544 KB 
#pragma GCC optimize("Ofast")
#include <bits/stdc++.h>
using namespace std;
//TRIE
struct node{
   node *nxt[26];
   int is;
   node(){
      is = 0;
      for(int i = 0;i<26;i++){
        nxt[i] = NULL;
      }
   }
};
void inser(string w,node *root){
    for(auto ch:w){
        if(root->nxt[ch-'a']==NULL){
            root->nxt[ch-'a'] = new node();
        }
        root=root->nxt[ch-'a'];
        root->is ++;
    }
}
vector<int> manacher_odd(string s) {
    int n = s.size();
    s = "$" + s + "^";
    vector<int> p(n + 2);
    int l = 1, r = 1;
    for(int i = 1; i <= n; i++) {
        p[i] = max(0, min(r - i, p[l + (r - i)]));
        while(s[i - p[i]] == s[i + p[i]]) {
            p[i]++;
        }
        if(i + p[i] > r) {
            l = i - p[i], r = i + p[i];
        }
    }
    return vector<int>(begin(p) + 1, end(p) - 1);
}
vector<int> manacher(string s) {
    string t;
    for(auto c: s) {
        t += string("#") + c;
    }
    auto res = manacher_odd(t + "#");
    return vector<int>(begin(res) + 1, end(res) - 1);
}
long long all = 0;
void dfs(node *root,int v,long long dep){
    all = max(all,root->is*(dep*2-v));
    for(int i = 0;i<26;i++){
        if(root->nxt[i]!=NULL){
            dfs(root->nxt[i],v,dep+1);
        }
    }
}
signed main(){
    ios_base::sync_with_stdio(false);cin.tie(0);cout.tie(0);
    node *rootOdd = new node();
    node *rootEven = new node();
    string s;cin>>s;
    vector<int> lol = manacher(s);
    for(int i = 0;i<lol.size();i++){
        long long x = lol[i]/2;
        if(i%2==0){
            int l = i/2;
            string ss;
            while(x--){
                ss+=s[l++];
            }
            inser(ss,rootOdd);
        }else{
            int l = i/2+1;
            string ss;
            while(x--){
                ss+=s[l++];
            }
            inser(ss,rootEven);
        }
    }
    dfs(rootEven,0,0);
    dfs(rootOdd,1,0);
    cout<<all<<"\n";
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:63:20: warning: comparison of integer expressions of different signedness: 'int' and 'std::vector<int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   63 |     for(int i = 0;i<lol.size();i++){
      |                   ~^~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 444 KB Output is correct
2 Correct 1 ms 468 KB Output is correct
3 Correct 3 ms 468 KB Output is correct
4 Correct 1 ms 468 KB Output is correct
5 Correct 3 ms 452 KB Output is correct
6 Correct 3 ms 468 KB Output is correct
7 Correct 1 ms 444 KB Output is correct
8 Correct 2 ms 468 KB Output is correct
9 Correct 1 ms 468 KB Output is correct
10 Correct 1 ms 340 KB Output is correct
11 Correct 1 ms 316 KB Output is correct
12 Correct 1 ms 468 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 252 ms 2736 KB Output is correct
2 Correct 130 ms 2740 KB Output is correct
3 Correct 329 ms 2988 KB Output is correct
4 Correct 260 ms 2760 KB Output is correct
5 Correct 3 ms 2616 KB Output is correct
6 Correct 9 ms 2616 KB Output is correct
7 Correct 35 ms 2676 KB Output is correct
8 Correct 1 ms 596 KB Output is correct
9 Correct 1 ms 596 KB Output is correct
10 Correct 2 ms 1964 KB Output is correct

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1078 ms 7600 KB Time limit exceeded
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Execution timed out 1066 ms 9544 KB Time limit exceeded
2 Halted 0 ms 0 KB -