oj.uz

Submission #959566

# Submission time Handle Problem Language Result Execution time Memory
959566 2024-04-08T12:46:45 Z jacobtpl Palindromes (APIO14_palindrome) C++17
100 / 100
 91 ms 75072 KB 
#include <algorithm>
#include <array>
#include <bitset>
#include <cassert>
#include <chrono>
#include <climits>
#include <cmath>
#include <complex>
#include <cstring>
#include <functional>
#include <iomanip>
#include <iostream>
#include <map>
#include <unordered_map>
#include <numeric>
#include <queue>
#include <random>
#include <set>
#include <vector>
using namespace std;

#define ll long long
#define pb push_back
#define mp make_pair
#define INF 1100000000
#define INFLL 1000000000000000000ll
#define ii pair<int,int>
#define sz(x) (int)(x).size()
#define all(x) (x).begin(),(x).end()
#define M1 1000000007ll
#define M2 1000000009ll
#define UQ(x) (x).resize(distance((x).begin(), unique(all(x))))
#define rep(i,a,b) for (int i = (a); i < (b); i++)
template<typename T> bool ckmax(T& a, T const& b) {return b>a?a=b,1:0;}
template<typename T> bool ckmin(T& a, T const& b) {return b<a?a=b,1:0;}


using vi = vector<int>;

struct PalTree {
    static const int ASZ = 26;
    struct node {
        array<int,ASZ> to = array<int,ASZ>();
        int len, link, oc = 0; // # occurrences of pal
        int slink = 0, diff = 0;
        array<int,2> seriesAns;
        node(int _len, int _link) : len(_len), link(_link) {}
    };
    string s = "@"; vector<array<int,2>> ans = {{0,INF}};
    vector<node> d = {{0,1},{-1,0}}; // dummy pals of len 0,-1
    int last = 1;
    int getLink(int v) {
        while (s[sz(s)-d[v].len-2] != s.back()) v = d[v].link;
        return v;
    }
    void updAns() { // serial path has O(log n) vertices
        ans.pb({INF,INF});
        for (int v = last; d[v].len > 0; v = d[v].slink) {
            d[v].seriesAns=ans[sz(s)-1-d[d[v].slink].len-d[v].diff];
            if (d[v].diff == d[d[v].link].diff) 
                rep(i,0,2) ckmin(d[v].seriesAns[i],
                            d[d[v].link].seriesAns[i]);
            // start of previous oc of link[v]=start of last oc of v
            rep(i,0,2) ckmin(ans.back()[i],d[v].seriesAns[i^1]+1);
        }
    }
    void addChar(char C) {
        s += C; int c = C-'a'; last = getLink(last);
        if (!d[last].to[c]) {
            d.emplace_back(d[last].len+2,d[getLink(d[last].link)].to[c]);
            d[last].to[c] = sz(d)-1;
            auto& z = d.back(); z.diff = z.len-d[z.link].len;
            z.slink = z.diff == d[z.link].diff 
                ? d[z.link].slink : z.link;
        } // max suf with different dif
        last = d[last].to[c]; ++d[last].oc;
        updAns();
    }
    void numOc() { for (int i=sz(d)-1;i>=2;i--) d[d[i].link].oc += d[i].oc; }
    ll solve() {
        numOc();
        ll ans = 0;
        for (auto &x:d) {
            ckmax(ans, (ll)x.len*(ll)x.oc);
        }
        return ans;
    }
};


int main() {
    cin.sync_with_stdio(0);
    cin.tie(0);
    string s;
    cin>>s;
    PalTree p;
    for (int i=0;i<sz(s);i++) {
        p.addChar(s[i]);
    }
    cout << p.solve() << '\n';
}
// int dp[maxn][2]; // dp(i,b) = min number of palindromes split with parity b

// int main() {
//     scanf("%s",t);
//     int l = strlen(t);
//     init();
//     for (int i = 0; i < l; i++) {
//         add_letter(t[i]-'a');
//         if (i == 0) {
//             dp[0][0] = INF;
//             dp[0][1] = 1;
//         } else {
            
//         }
//     }
//     printf("%s\n", t);
// }

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 604 KB Output is correct
2 Correct 1 ms 604 KB Output is correct
3 Correct 1 ms 604 KB Output is correct
4 Correct 1 ms 604 KB Output is correct
5 Correct 1 ms 604 KB Output is correct
6 Correct 0 ms 728 KB Output is correct
7 Correct 1 ms 604 KB Output is correct
8 Correct 0 ms 604 KB Output is correct
9 Correct 0 ms 452 KB Output is correct
10 Correct 1 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 1 ms 604 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 2736 KB Output is correct
2 Correct 3 ms 2740 KB Output is correct
3 Correct 2 ms 2740 KB Output is correct
4 Correct 2 ms 2740 KB Output is correct
5 Correct 2 ms 2592 KB Output is correct
6 Correct 2 ms 2740 KB Output is correct
7 Correct 2 ms 2740 KB Output is correct
8 Correct 1 ms 604 KB Output is correct
9 Correct 1 ms 604 KB Output is correct
10 Correct 2 ms 1480 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 16 ms 19656 KB Output is correct
2 Correct 15 ms 18604 KB Output is correct
3 Correct 15 ms 18632 KB Output is correct
4 Correct 20 ms 18632 KB Output is correct
5 Correct 19 ms 18628 KB Output is correct
6 Correct 17 ms 19132 KB Output is correct
7 Correct 16 ms 19068 KB Output is correct
8 Correct 3 ms 2004 KB Output is correct
9 Correct 6 ms 5904 KB Output is correct
10 Correct 17 ms 19144 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 57 ms 72768 KB Output is correct
2 Correct 57 ms 74932 KB Output is correct
3 Correct 54 ms 72872 KB Output is correct
4 Correct 61 ms 72784 KB Output is correct
5 Correct 91 ms 72876 KB Output is correct
6 Correct 67 ms 75072 KB Output is correct
7 Correct 46 ms 39748 KB Output is correct
8 Correct 9 ms 5960 KB Output is correct
9 Correct 10 ms 5840 KB Output is correct
10 Correct 51 ms 39080 KB Output is correct
11 Correct 56 ms 72868 KB Output is correct
12 Correct 12 ms 10196 KB Output is correct