oj.uz

Submission #921429

# Submission time Handle Problem Language Result Execution time Memory
921429 2024-02-03T20:18:42 Z AVIJIT_BISWAS Palindromes (APIO14_palindrome) C++14
0 / 100
 17 ms 35504 KB 
#include <bits/stdc++.h>
using namespace std;
#define ll long long

struct PalindromicTree {
  struct node {
    int nxt[26], len, link, occ;
  };
  string s;
  vector<node> t;
  int sz, last;
  PalindromicTree() {}
  PalindromicTree(string _s) {
    s = _s;
    int n = s.size();
    t.clear();
    t.resize(n + 9);
    sz = 2, last = 2;
    t[1].len = -1, t[1].link = 1;
    t[2].len = 0, t[2].link = 1;
  }
  int extend(int pos) { // returns 1 if it creates a new palindrome
    int cur = last, curlen = 0;
    int ch = s[pos] - 'a';
    while (1) {
      curlen = t[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) break;
      cur = t[cur].link;
    }
    if (t[cur].nxt[ch]) {
      last = t[cur].nxt[ch];
      return 0;
    }
    sz++;
    last = sz;
    t[sz].len = t[cur].len + 2;
    t[cur].nxt[ch] = sz;

    t[last].occ = 1;

    if (t[sz].len == 1) {
      t[sz].link = 2;
      return 1;
    }
    while (1) {
      cur = t[cur].link;
      curlen = t[cur].len;
      if (pos - 1 - curlen >= 0 && s[pos - 1 - curlen] == s[pos]) {
        t[sz].link = t[cur].nxt[ch];
        break;
      }
    }


    return 1;
  }
}T;


void solve() {
  string s; cin >> s;
  T = PalindromicTree(s);
  int n = s.size();

  for(int i = 0; i < n; i++){
    T.extend(i);
  }


  ll ans = 0;
  for(int i = T.sz; i > 2; i--) {
    T.t[T.t[i].link].occ  += T.t[i].occ;
    ans = max(ans, 1ll * T.t[i].occ * T.t[i].len);
  }

  cout << ans << '\n';

}

int32_t main() {
    ios_base::sync_with_stdio(false); cin.tie(nullptr);int t = 1;

    // cin >> t;

    for(int i = 1; i <= t; i++){
    //cout << "-----Case:" << i << "-----\n";
        solve();
    }

    return 0;
}

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 0 ms 348 KB Output is correct
2 Correct 0 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Correct 0 ms 348 KB Output is correct
11 Correct 0 ms 348 KB Output is correct
12 Correct 0 ms 344 KB Output is correct
13 Correct 1 ms 348 KB Output is correct
14 Incorrect 0 ms 388 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 344 KB Output is correct
2 Correct 0 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 348 KB Output is correct
7 Correct 0 ms 348 KB Output is correct
8 Correct 0 ms 348 KB Output is correct
9 Correct 0 ms 348 KB Output is correct
10 Incorrect 0 ms 348 KB Output isn't correct
11 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 1628 KB Output is correct
2 Correct 1 ms 1628 KB Output is correct
3 Correct 1 ms 1628 KB Output is correct
4 Correct 1 ms 1628 KB Output is correct
5 Correct 1 ms 1628 KB Output is correct
6 Correct 1 ms 1628 KB Output is correct
7 Correct 1 ms 1628 KB Output is correct
8 Incorrect 1 ms 1632 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 12124 KB Output is correct
2 Correct 4 ms 12124 KB Output is correct
3 Correct 4 ms 12124 KB Output is correct
4 Correct 4 ms 12120 KB Output is correct
5 Correct 4 ms 12124 KB Output is correct
6 Correct 5 ms 12120 KB Output is correct
7 Correct 5 ms 12376 KB Output is correct
8 Incorrect 4 ms 12124 KB Output isn't correct
9 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 15 ms 35300 KB Output is correct
2 Correct 17 ms 35300 KB Output is correct
3 Correct 15 ms 35504 KB Output is correct
4 Correct 16 ms 35400 KB Output is correct
5 Correct 16 ms 35300 KB Output is correct
6 Correct 16 ms 35296 KB Output is correct
7 Correct 17 ms 35300 KB Output is correct
8 Incorrect 13 ms 35300 KB Output isn't correct
9 Halted 0 ms 0 KB -