Submission #317610

#	Time	Username	Problem	Language	Result	Execution time	Memory
317610		wwdd	Palindromes (APIO14_palindrome)	C++14	100 / 100	247 ms	72756 KiB

palindrome

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef vector<int> vi;
typedef vector<ll> vl;
const int MA = 26;
const int LOL = 21;
vi tr[MA];
vi anc[LOL];
vl so;
void adn() {
	for(int i=0;i<MA;i++) {
		tr[i].push_back(-1);
	}
	for(int i=0;i<LOL;i++) {
		anc[i].push_back(-1);
	}
	so.push_back(0);
}
int mov(int u, int go) {
	if(tr[go][u] == -1) {
		int nx = tr[go].size();
		adn();
		tr[go][u] = nx;
		anc[0][nx] = u;
		for(int i=1;i<LOL;i++) {
			anc[i][nx] = anc[i-1][anc[i-1][nx]];
		}
		return nx;
	} else {
		return tr[go][u];
	}
}
int ganc(int u, int an) {
	for(int i=LOL-1;i>=0;i--) {
		if(an&(1<<i)) {
			u = anc[i][u];
		}
	}
	return u;
}
vi ra,rb,wa,wb;
void manc(const string& s) {
	ra.assign(s.size(),-1);
	rb.assign(s.size(),-1);
	wa.assign(s.size(),-1);
	wb.assign(s.size(),-1);
	int n = s.size();
	for(int i=0,l=0,r=-1;i<n;i++) {
		int st;
		int k;
		if(i > r) {
			k = 1;
			st = mov(0,s[i]-'a');
		} else {
			k = min(ra[l+r-i],r-i+1);
			st = ganc(wa[l+r-i],ra[l+r-i]-k);
		}
		while(i-k >= 0 && i+k < n && s[i-k] == s[i+k]) {
			st = mov(st,s[i+k]-'a');
			k++;
		}
		ra[i] = k;k--;
		wa[i] = st;
		if(i+k > r) {
			l = i-k;
			r = i+k;
		}
		so[st]++;
	}
	for(int i=0,l=0,r=-1;i<n;i++) {
		int st;
		int k;
		if(i > r) {
			k = 0;
			st = 1;
		} else {
			k = min(rb[r+l-i+1],r-i+1);
			st = ganc(wb[r+l-i+1],rb[r+l-i+1]-k);
		}
		while(i-k-1 >= 0 && i+k < n && s[i-k-1] == s[i+k]) {
			st = mov(st,s[i+k]-'a');
			k++;
		}
		rb[i] = k;k--;
		wb[i] = st;
		if(i+k > r) {
			l = i-k-1;
			r = i+k;
		}
		so[st]++;
	}
}
void dfa(int u) {
	for(int i=0;i<MA;i++) {
		int v = tr[i][u];
		if(v == -1) {continue;}
		dfa(v);
		so[u] += so[v];
	}
}
ll dfb(int u, ll len) {
	ll res = 0;
	for(int i=0;i<MA;i++) {
		int v = tr[i][u];
		if(v == -1) {continue;}
		res = max(res,dfb(v,len+2));
	}
	res = max(res,len*so[u]);
	return res;
}
int main() {
	ios::sync_with_stdio(0);cin.tie(0);
	for(int i=0;i<MA;i++) {
		tr[i].push_back(-1);
		tr[i].push_back(-1);
	}
	for(int i=0;i<LOL;i++) {
		anc[i].push_back(0);
		anc[i].push_back(1);
	}
	so.push_back(0);
	so.push_back(0);
	string s;
	cin >> s;
	manc(s);
	dfa(0);dfa(1);
	ll res = max(dfb(0,-1),dfb(1,0));
	cout << res << '\n';
}

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