Submission #50340

#	Time	Username	Problem	Language	Result	Execution time	Memory
50340		szawinis	Palindromes (APIO14_palindrome)	C++17	100 / 100	99 ms	54308 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
#define fori(i, a, b) for(int i = int(a); i <= int(b); ++i)
#define rofi(i, b, a) fori(int i = int(b); i >= int(a); --i)
#define foreach(it, a) for(auto &it: a)
#define pb push_back
#define epb emplace_back
#define mp make_pair
#define all(a) a.begin(), a.end()
#define csz(a) int(a.size())
#define load(a, v) fill(begin(a), end(a), v);
using ll = long long;
const ll MOD = 1e9+7, LINF = 1e17;
const int INF = 1e9+1;
const double EPS = 1e-10;
const int dx[4] = {-1, 0, 1, 0}, dy[4] = {0, 1, 0, -1};
// END TEMPLATE

struct Paltree {
	vector<int> s, len, link, cnt, deg;
	vector<vector<int> > nxt;
	int last = 0;
	Paltree() {
		len.pb(0), len.pb(-1);
		link.pb(1), link.pb(1);
		nxt.pb(vector<int>(26)), nxt.pb(vector<int>(26));
		cnt.pb(0), cnt.pb(0);
		deg.pb(0), deg.pb(0); // not actually 0 but who cares
	}
	int get_link(int v) {
		while(csz(s) - len[v] - 2 < 0 || s.back() != s[csz(s) - len[v] - 2])
			v = link[v];
		return v;
	}
	void update(int c) {
		s.pb(c);
		last = get_link(last);
		if(!nxt[last][c]) {
			len.pb(len[last] + 2);
			int strict_link = nxt[get_link(link[last])][c];
			link.pb(strict_link);
			nxt.pb(vector<int>(26));
			nxt[last][c] = csz(nxt) - 1;
			// cout << "strict link" << strict_link << endl;
			
			// queries
			cnt.pb(1);
			deg.pb(0);
			++deg[strict_link];
		} else ++cnt[nxt[last][c]];
		last = nxt[last][c];
	}
};

int n;
string s;
Paltree t;
ll ans;
int main() {
	ios::sync_with_stdio(false);
	cin.tie(0);
	cin >> s;
	n = s.length();
	fori(i, 0, n-1) t.update(s[i] - 'a');
	queue<int> q;
	fori(i, 0, t.nxt.size()-1) if(!t.deg[i]) q.push(i);
	//
	// fori(i, 0, csz(t.nxt) - 1) cout << t.deg[i] << ' ';
	// cout << endl;
	//
	while(!q.empty()) {
		int i = q.front();
		q.pop();
		ans = max(1ll * t.len[i] * t.cnt[i], ans);
		// cout << i << ' ' << t.len[i] << ' ' << t.cnt[i] << endl;
		t.cnt[t.link[i]] += t.cnt[i];
		--t.deg[t.link[i]];
		if(!t.deg[t.link[i]]) q.push(t.link[i]);
	}
	cout << ans;
}

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