oj.uz

Submission #317610

# Submission time Handle Problem Language Result Execution time Memory
317610 2020-10-30T04:05:36 Z wwdd Palindromes (APIO14_palindrome) C++14
100 / 100
 247 ms 72756 KB 
#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.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 384 KB Output is correct
2 Correct 1 ms 384 KB Output is correct
3 Correct 1 ms 384 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 512 KB Output is correct
6 Correct 1 ms 384 KB Output is correct
7 Correct 1 ms 384 KB Output is correct
8 Correct 1 ms 384 KB Output is correct
9 Correct 1 ms 384 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 384 KB Output is correct
12 Correct 1 ms 384 KB Output is correct
13 Correct 1 ms 384 KB Output is correct
14 Correct 1 ms 384 KB Output is correct
15 Correct 1 ms 384 KB Output is correct
16 Correct 1 ms 384 KB Output is correct
17 Correct 1 ms 384 KB Output is correct
18 Correct 1 ms 384 KB Output is correct
19 Correct 1 ms 384 KB Output is correct
20 Correct 1 ms 384 KB Output is correct
21 Correct 1 ms 384 KB Output is correct
22 Correct 1 ms 384 KB Output is correct
23 Correct 1 ms 384 KB Output is correct
24 Correct 1 ms 416 KB Output is correct
25 Correct 1 ms 384 KB Output is correct
26 Correct 1 ms 384 KB Output is correct
27 Correct 1 ms 384 KB Output is correct
28 Correct 1 ms 384 KB Output is correct
29 Correct 1 ms 384 KB Output is correct
30 Correct 1 ms 384 KB Output is correct
31 Correct 1 ms 384 KB Output is correct
32 Correct 1 ms 384 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 1 ms 640 KB Output is correct
2 Correct 1 ms 512 KB Output is correct
3 Correct 1 ms 640 KB Output is correct
4 Correct 1 ms 512 KB Output is correct
5 Correct 1 ms 640 KB Output is correct
6 Correct 1 ms 640 KB Output is correct
7 Correct 1 ms 640 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 512 KB Output is correct
10 Correct 1 ms 384 KB Output is correct
11 Correct 1 ms 416 KB Output is correct
12 Correct 1 ms 640 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 7 ms 3712 KB Output is correct
2 Correct 7 ms 3584 KB Output is correct
3 Correct 7 ms 3712 KB Output is correct
4 Correct 7 ms 3584 KB Output is correct
5 Correct 7 ms 3712 KB Output is correct
6 Correct 7 ms 3584 KB Output is correct
7 Correct 7 ms 3456 KB Output is correct
8 Correct 1 ms 640 KB Output is correct
9 Correct 1 ms 640 KB Output is correct
10 Correct 5 ms 2304 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 82 ms 25436 KB Output is correct
2 Correct 71 ms 23892 KB Output is correct
3 Correct 77 ms 25304 KB Output is correct
4 Correct 73 ms 24152 KB Output is correct
5 Correct 72 ms 24340 KB Output is correct
6 Correct 59 ms 18520 KB Output is correct
7 Correct 63 ms 20056 KB Output is correct
8 Correct 4 ms 2176 KB Output is correct
9 Correct 18 ms 8444 KB Output is correct
10 Correct 63 ms 21532 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 246 ms 72756 KB Output is correct
2 Correct 234 ms 65836 KB Output is correct
3 Correct 247 ms 72496 KB Output is correct
4 Correct 241 ms 66608 KB Output is correct
5 Correct 236 ms 71292 KB Output is correct
6 Correct 213 ms 60136 KB Output is correct
7 Correct 173 ms 56292 KB Output is correct
8 Correct 11 ms 5768 KB Output is correct
9 Correct 11 ms 5896 KB Output is correct
10 Correct 175 ms 62056 KB Output is correct
11 Correct 236 ms 72752 KB Output is correct
12 Correct 27 ms 12936 KB Output is correct