제출 #1119475

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1119475		vjudge1	회문 (APIO14_palindrome)	C++17	100 / 100	722 ms	55976 KiB

palindrome

#include <bits/stdc++.h>
#define pb push_back
#define sz(x) (int)x.size()
#define all(x) x.begin(), x.end()
#define f first
#define s second

using namespace std;
using ll = long long;
using pii = pair <int, int>;
using vi = vector <int>;
const int N = 3e5 + 5, base[] = {301991, 400457}, mod[] = {(int)1e9 + 7, 998244353};

int n, pw[N][2], len[N], cnt[N];
ll ans;
bool used[N];
pii h[N];
vector <int> g[N];
string s;

pii get(int l, int r) {
	if (l > r)
		return {0, 0};
	if (!l)
		return h[r];
	int f = h[r].f - (h[l - 1].f * 1ll * pw[r - l + 1][0] % mod[0]);
	if (f < 0) f += mod[0];
	int se = h[r].s - (h[l - 1].s * 1ll * pw[r - l + 1][1] % mod[1]);
	if (se < 0) se += mod[1];
	return {f, se};
}

void dfs(int v) {
	used[v] = 1;
	for (auto to : g[v]) {
		if (used[to])
			continue;
		dfs(to);
		cnt[v] += cnt[to];
	}
	/*cout << v << ' ' << len[v] << ' ' << cnt[v] << '\n';
	cout << "sons\n";
	for (auto to : g[v]) {
		cout << to << ' ';
	}
	cout << '\n';*/
	ans = max(ans, 1ll * cnt[v] * len[v]);
}

int main() {
	ios :: sync_with_stdio(0);
	cin.tie(0);
	cin >> s;
	n = sz(s);
	h[0].f = s[0];
	h[0].s = s[0];
	pw[0][0] = pw[0][1] = 1;
	for (int i = 1; i <= n; ++i) {
		if (i < n) {
			h[i].f = (h[i - 1].f * 1ll * base[0] + s[i]) % mod[0];
			h[i].s = (h[i - 1].s * 1ll * base[1] + s[i]) % mod[1];
		}
		pw[i][0] = pw[i - 1][0] * 1ll * base[0] % mod[0];
		pw[i][1] = pw[i - 1][1] * 1ll * base[1] % mod[1];
	}
	map <pii, int> ind;
	ind[{0, 0}] = 0;
	int sz = 0;
	array <vi, 2> p = {vi(n + 1), vi(n)};
	for (int z = 0; z < 2; ++z) {
		for (int i = 0, l = 0, r = 0; i < n; ++i) {
			int t = r - i + !z;
			if (i < r) 
				p[z][i] = min(t, p[z][l + t]);
			int L = i - p[z][i], R = i + p[z][i] - !z;
			pii cur = get(L, R);
			if (!ind.count(cur)) {
				ind[cur] = ++sz;
				len[ind[cur]] = R - L + 1;
			}
			if (L == R) 
				g[0].pb(ind[cur]);
			while (L >= 1 && R + 1 < n && s[L - 1] == s[R + 1]) {
				p[z][i]++, L--, R++;
				pii prv = cur;
				cur = get(L, R);
				if (!ind.count(cur)) {
					ind[cur] = ++sz;
					len[ind[cur]] = R - L + 1;
				}
				//cout << "wtf " << ind[prv] << ' ' << ind[cur] << '\n';
				g[ind[prv]].pb(ind[cur]);
			}
			cnt[ind[cur]]++;
			if (R > r) l = L, r = R;
		}
	}
	dfs(0);
	cout << ans;
	return 0;
}

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