oj.uz

Submission #116537

# Submission time Handle Problem Language Result Execution time Memory
116537 2019-06-12T19:31:17 Z pbt17 Palindromes (APIO14_palindrome) C++14
0 / 100
 36 ms 20372 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<300000, 26> t;
  string s; cin >> s;
  for (char c : s) t.put(c);
  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
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 Incorrect 2 ms 384 KB Output isn't correct
4 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 2 ms 416 KB Output is correct
2 Correct 2 ms 512 KB Output is correct
3 Correct 2 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 384 KB Output is correct
9 Incorrect 2 ms 484 KB Output isn't correct
10 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 3 ms 1152 KB Output is correct
2 Correct 5 ms 1536 KB Output is correct
3 Correct 4 ms 1664 KB Output is correct
4 Correct 4 ms 1536 KB Output is correct
5 Incorrect 4 ms 1536 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 12 ms 7168 KB Output is correct
2 Correct 16 ms 9700 KB Output is correct
3 Correct 19 ms 12792 KB Output is correct
4 Correct 19 ms 12792 KB Output is correct
5 Incorrect 18 ms 12800 KB Output isn't correct
6 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 36 ms 20372 KB Output isn't correct
2 Halted 0 ms 0 KB -