oj.uz

Submission #615465

# Submission time Handle Problem Language Result Execution time Memory
615465 2022-07-31T09:35:57 Z abc864197532 Palindromes (APIO14_palindrome) C++17
73 / 100
 46 ms 48172 KB 
#include <bits/stdc++.h>
using namespace std;
#define lli long long int
#define mp make_pair
#define pb push_back
#define eb emplace_back
#define pii pair <int, int>
#define X first
#define Y second
#define all(x) x.begin(), x.end()
#define rall(x) x.rbegin(), x.rend()
void abc() {cout << endl;}
template <typename T, typename ...U> void abc(T a, U ...b) {
    cout << a << ' ', abc(b...);
}
template <typename T> void printv(T l, T r) {
    for (; l != r; ++l) cout << *l << " \n"[l + 1 == r];
}
template <typename A, typename B> istream& operator >> (istream& o, pair<A, B> &a) {
    return o >> a.X >> a.Y;
}
template <typename A, typename B> ostream& operator << (ostream& o, pair<A, B> a) {
    return o << '(' << a.X << ", " << a.Y << ')';
}
template <typename T> ostream& operator << (ostream& o, vector<T> a) {
    bool is = false;
    if (a.empty()) return o << "{}";
    for (T i : a) {o << (is ? ' ' : '{'), is = true, o << i;}
    return o << '}';
}
template <typename T> struct vv : vector <vector <T>> {
    vv (int n, int m, T v) : vector <vector <T>> (n, vector <T>(m, v)) {}
    vv (int n, int m) : vector <vector <T>> (n, vector <T>(m)) {}
    vv () {}
};
template <typename T> struct vvv : vector <vv <T>> {
    vvv (int n, int m, int k, T v) : vector <vv <T>> (n, vv <T>(m, k, v)) {}
    vvv (int n, int m, int k) : vector <vv <T>> (n, vv <T>(m, k)) {}
    vvv () {}
};
#ifdef Doludu
#define test(args...) abc("[" + string(#args) + "]", args)
#define owo freopen("input.txt", "r", stdin), freopen("output.txt", "w", stdout)
#else
#define test(args...) void(0)
#define owo ios::sync_with_stdio(false); cin.tie(0)
#endif
const int mod = 998244353, N = 200005, logN = 18, G = 3;

struct PAM {
    int ch[N][26], cnt[N], fail[N], len[N], sz;
    string s;
    // 0 -> even root, 1 -> odd root
    PAM (string _s) : s(_s) {
        sz = 0;
        extend(), extend();
        len[0] = 0, fail[0] = 1, len[1] = -1;
        int lst = 1;
        for (int i = 0; i < s.length(); ++i) {
            while (s[i - len[lst] - 1] != s[i])
                lst = fail[lst];
            if (!ch[lst][s[i] - 'a'])  {
                int idx = extend();
                len[idx] = len[lst] + 2;
                int now = fail[lst];
                while (s[i - len[now] - 1] != s[i])
                    now = fail[now];
                fail[idx] = ch[now][s[i] - 'a'];
                ch[lst][s[i] - 'a'] = idx;
            }
            lst = ch[lst][s[i] - 'a'], cnt[lst]++;
        }
    }
    int extend() {
        fill(ch[sz], ch[sz] + 26, 0), sz++;
        return sz - 1;
    }
    lli solve() {
        for (int i = sz - 1; i > 1; --i) {
            cnt[fail[i]] += cnt[i];
        }
        lli ans = 0;
        for (int i = 2; i < sz; ++i) {
            ans = max(ans, 1ll * len[i] * cnt[i]);
        }
        return ans;
    }
};

int main () {
    owo;
    string s;
    cin >> s;
    PAM solver(s);
    cout << solver.solve() << '\n';
}

Compilation message

palindrome.cpp: In constructor 'PAM::PAM(std::string)':
palindrome.cpp:59:27: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   59 |         for (int i = 0; i < s.length(); ++i) {
      |                         ~~^~~~~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 9 ms 22996 KB Output is correct
2 Correct 9 ms 23016 KB Output is correct
3 Correct 9 ms 22984 KB Output is correct
4 Correct 10 ms 22908 KB Output is correct
5 Correct 10 ms 22996 KB Output is correct
6 Correct 9 ms 23024 KB Output is correct
7 Correct 11 ms 22996 KB Output is correct
8 Correct 9 ms 22968 KB Output is correct
9 Correct 10 ms 22996 KB Output is correct
10 Correct 15 ms 22976 KB Output is correct
11 Correct 14 ms 22900 KB Output is correct
12 Correct 12 ms 23012 KB Output is correct
13 Correct 10 ms 22996 KB Output is correct
14 Correct 10 ms 22996 KB Output is correct
15 Correct 9 ms 23012 KB Output is correct
16 Correct 13 ms 22924 KB Output is correct
17 Correct 9 ms 22936 KB Output is correct
18 Correct 12 ms 22916 KB Output is correct
19 Correct 12 ms 22996 KB Output is correct
20 Correct 10 ms 22948 KB Output is correct
21 Correct 11 ms 22972 KB Output is correct
22 Correct 11 ms 23040 KB Output is correct
23 Correct 10 ms 22976 KB Output is correct
24 Correct 13 ms 22980 KB Output is correct
25 Correct 11 ms 22984 KB Output is correct
26 Correct 14 ms 23016 KB Output is correct
27 Correct 13 ms 22996 KB Output is correct
28 Correct 10 ms 23016 KB Output is correct
29 Correct 11 ms 22916 KB Output is correct
30 Correct 10 ms 23020 KB Output is correct
31 Correct 10 ms 23020 KB Output is correct
32 Correct 11 ms 22996 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 11 ms 22996 KB Output is correct
2 Correct 10 ms 22996 KB Output is correct
3 Correct 10 ms 22996 KB Output is correct
4 Correct 11 ms 22996 KB Output is correct
5 Correct 13 ms 22896 KB Output is correct
6 Correct 14 ms 22964 KB Output is correct
7 Correct 11 ms 22936 KB Output is correct
8 Correct 12 ms 22996 KB Output is correct
9 Correct 13 ms 22996 KB Output is correct
10 Correct 12 ms 22964 KB Output is correct
11 Correct 12 ms 22940 KB Output is correct
12 Correct 12 ms 23016 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23028 KB Output is correct
2 Correct 12 ms 23064 KB Output is correct
3 Correct 13 ms 23020 KB Output is correct
4 Correct 10 ms 23028 KB Output is correct
5 Correct 11 ms 22996 KB Output is correct
6 Correct 14 ms 23024 KB Output is correct
7 Correct 12 ms 23028 KB Output is correct
8 Correct 12 ms 23048 KB Output is correct
9 Correct 10 ms 22996 KB Output is correct
10 Correct 11 ms 22972 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 14 ms 23372 KB Output is correct
2 Correct 14 ms 23388 KB Output is correct
3 Correct 17 ms 23392 KB Output is correct
4 Correct 15 ms 23408 KB Output is correct
5 Correct 15 ms 23412 KB Output is correct
6 Correct 14 ms 23348 KB Output is correct
7 Correct 15 ms 23360 KB Output is correct
8 Correct 14 ms 23380 KB Output is correct
9 Correct 13 ms 23408 KB Output is correct
10 Correct 15 ms 23380 KB Output is correct

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 46 ms 48172 KB Execution killed with signal 11
2 Halted 0 ms 0 KB -