oj.uz

Submission #116538

# Submission time Handle Problem Language Result Execution time Memory
116538 2019-06-12T19:37:01 Z pbt17 Palindromes (APIO14_palindrome) C++14
23 / 100
 12 ms 2076 KB 
#include <bits/stdc++.h>
using namespace std;
 
template<int N_, int A> struct pal_tree {
 
  const static int N = N_ + 2;
 
  int n, s[N], suff[N];
  int k, len[N], occ[N], to[N][A], link[N];
 
  pal_tree() : n(0), k(0) {
    palindrome(0, 1);
    palindrome(-1, 1);
    letter(-1, 0);
  }
 
  int palindrome(int l, int suf) {
    len[k] = l;
    occ[k] = 0;
    fill_n(to[k], A, 0);
    link[k] = suf;
    return k++;
  }
 
  int letter(int val, int suf) {
    s[n] = val;
    suff[n] = suf;
    occ[suf]++;
    return n++;
  }
 
  int trim(int u) {
    while (s[n - 1 - len[u]] != s[n]) {
      u = link[u];
    }
    return u;
  }
 
  void put(int c) {
    s[n] = c; // don't delete :P
    int u = trim(suff[n - 1]);
    if (!to[u][c]) {
      int v = trim(link[u]);
      to[u][c] = palindrome(len[u] + 2, to[v][c]);
    }
    letter(c, to[u][c]);
  }
 
  int distinct() {
    return k - 2;
  }
 
  void occurrences() {
    for (int u = k - 1; u > 1; u--) {
      occ[link[u]] += occ[u];
    }
  }
 
  void clear() {
    n = 1;
  }
};
 
int main() {
  pal_tree<3000, 26> t;
  string s; cin >> s;
  for (char c : s) t.put(c - 'a');
  long long ans = 1;
  t.occurrences();
  for (int i = 2; i < t.k; i++) {
    ans = max(ans, (long long) t.occ[i] * t.len[i]);
  }
  cout << ans << endl;
}

Subtask #1
8.0 / 8.0

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

Subtask #2
15.0 / 15.0

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

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Runtime error 3 ms 1152 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Runtime error 6 ms 1664 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Runtime error 12 ms 2076 KB Execution killed with signal 11 (could be triggered by violating memory limits)
2 Halted 0 ms 0 KB -