oj.uz

Submission #745149

# Submission time Handle Problem Language Result Execution time Memory
745149 2023-05-19T13:03:13 Z ACE_ Palindromes (APIO14_palindrome) C++14
100 / 100
 73 ms 87768 KB 
#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N = 3e5 + 5;
int cnt[N], in[N], last = 0, cur = 1;
struct eer {
    int e[26], suf, sz;
} t[N];
vector<int> V[N];
string s;
void add(int i) {
    while(true) {
        if(s[i] == s[i - t[last].sz - 1]) {
            if(t[last].e[s[i] - 'a']) {
                last = t[last].e[s[i] - 'a'];
                ++cnt[last];
                return;
            }
            t[last].e[s[i] - 'a'] = ++cur;
            t[cur].sz = t[last].sz + 2;
            cnt[cur] = 1;
            break;
        }
        last = t[last].suf;
    }
    int id = t[last].suf;
    if(last == 0) {
        t[cur].suf = 1;
        last = cur;
        return;
    }
    last = cur;

    while(true) {
        if(s[i] == s[i - t[id].sz - 1]) {
            t[cur].suf = t[id].e[s[i] - 'a'];
            V[cur].push_back(t[id].e[s[i] - 'a']);
            ++in[t[id].e[s[i] - 'a']];
            return;

        }
        id = t[id].suf;
    }
}
main(){
    cin >> s;
    t[0].sz = -1;
    t[1].sz = 0;
    cur = 1; last = 0;
    for(int i = 0; i < s.size(); i++) {
        add(i);
    }
    queue<int> q;
    for(int i = 1; i <= cur; i++) {
        if(!in[i]) q.push(i);
    }
    int ans = 0;
    while(q.size()) {
        int x = q.front();
        q.pop();
        ans = max(ans, t[x].sz * cnt[x]);
        for(int i = 0; i < V[x].size(); i++) {
            cnt[V[x][i]] += cnt[x];
            --in[V[x][i]];
            if(!in[V[x][i]]) q.push(V[x][i]);
        }
    }
    cout << ans;

 }

Compilation message

palindrome.cpp:45:1: warning: ISO C++ forbids declaration of 'main' with no type [-Wreturn-type]
   45 | main(){
      | ^~~~
palindrome.cpp: In function 'int main()':
palindrome.cpp:50:22: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   50 |     for(int i = 0; i < s.size(); i++) {
      |                    ~~^~~~~~~~~~
palindrome.cpp:62:26: warning: comparison of integer expressions of different signedness: 'long long int' and 'std::vector<long long int>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   62 |         for(int i = 0; i < V[x].size(); i++) {
      |                        ~~^~~~~~~~~~~~~

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 6 ms 9940 KB Output is correct
2 Correct 6 ms 9940 KB Output is correct
3 Correct 6 ms 9940 KB Output is correct
4 Correct 6 ms 9940 KB Output is correct
5 Correct 6 ms 9940 KB Output is correct
6 Correct 6 ms 9940 KB Output is correct
7 Correct 6 ms 10068 KB Output is correct
8 Correct 5 ms 7432 KB Output is correct
9 Correct 5 ms 7380 KB Output is correct
10 Correct 6 ms 9172 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 26 ms 34004 KB Output is correct
2 Correct 25 ms 34064 KB Output is correct
3 Correct 24 ms 34076 KB Output is correct
4 Correct 29 ms 34096 KB Output is correct
5 Correct 27 ms 34052 KB Output is correct
6 Correct 22 ms 26816 KB Output is correct
7 Correct 23 ms 29944 KB Output is correct
8 Correct 9 ms 7764 KB Output is correct
9 Correct 12 ms 13780 KB Output is correct
10 Correct 23 ms 30016 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 73 ms 87396 KB Output is correct
2 Correct 71 ms 87392 KB Output is correct
3 Correct 64 ms 87476 KB Output is correct
4 Correct 68 ms 87396 KB Output is correct
5 Correct 72 ms 87768 KB Output is correct
6 Correct 65 ms 78816 KB Output is correct
7 Correct 69 ms 74272 KB Output is correct
8 Correct 16 ms 8424 KB Output is correct
9 Correct 18 ms 8368 KB Output is correct
10 Correct 63 ms 73304 KB Output is correct
11 Correct 64 ms 87684 KB Output is correct
12 Correct 20 ms 15588 KB Output is correct