Submission #1250849

#	Time	Username	Problem	Language	Result	Execution time	Memory
1250849		nhan	Palindromes (APIO14_palindrome)	C++20	100 / 100	32 ms	45264 KiB

palindrome

#include <bits/stdc++.h>

using namespace std;


typedef long long ll;

const int INF = 0x3f3f3f3f;
const ll LINF = 0x3f3f3f3f3f3f3f3fll;

struct eertree {
	vector<vector<int>> t;
	int n, last, sz;
	vector<int> s, len, link, qt;

	eertree(int N) {
        t = vector<vector<int>>(N+2,vector<int>(26,0));
		s = len = link = qt = vector<int>(N+2);
		s[0] = -1;
		link[0] = 1, len[0] = 0, link[1] = 1, len[1] = -1;
		sz = 2, last = 0, n = 1;
	}

	void add(char c) {
		s[n++] = c -= 'a';
		while (s[n-len[last]-2] != c) last = link[last];
		if (!t[last][c]) {
			int prev = link[last];
			while (s[n-len[prev]-2] != c) prev = link[prev];
			link[sz] = t[prev][c];
			len[sz] = len[last]+2;
			t[last][c] = sz++;
		}
		qt[last = t[last][c]]++;
	}
	int size() { return sz-2; }
	ll propagate() {
		ll ret = 0;
		for (int i = n; i > 1; i--) {
            //cout<<link[i]<<'\n';
			qt[link[i]] += qt[i];
			ret += qt[i];
		}
		return ret;
	}
};


int main() {
  ios_base::sync_with_stdio(0);cin.tie(0);

  string s; cin >> s;
  const int n = s.size();
  eertree et(n);

  for (char c : s) et.add(c);

  et.propagate();

  ll ans = 0;
  for (int i = 0; i < n + 2; i++) {
    ans = max(ans, ((ll) et.qt[i]) * et.len[i]);
  }
  cout << ans << '\n';

  return 0;
}

• Subtask 1: 8 / 8
• Subtask 2: 15 / 15
• Subtask 3: 24 / 24
• Subtask 4: 26 / 26
• Subtask 5: 27 / 27