oj.uz

Submission #530838

# Submission time Handle Problem Language Result Execution time Memory
530838 2022-02-26T23:22:42 Z new_acc Palindromes (APIO14_palindrome) C++14
100 / 100
 159 ms 92364 KB 
#include<bits/stdc++.h>
#define fi first
#define se second
#define pitem item*
using namespace std;
typedef long long ll;
typedef vector<ll> vi;
typedef vector<ll> vl;
struct item{
	pitem fail;
	int l,il;
	pitem g[27];
};
const int N=3e5+10;
string s;
item *k1,*k2;
vector<pitem> k[N];
pitem add(int ind,pitem curr){
	while(curr!=nullptr){
		if(ind+1>=(curr->l)+2 and s[ind-(curr->l)-1]==s[ind]) break;
		curr=curr->fail;
	}
	if(curr->g[int(s[ind])-96]!=nullptr) {
		curr->g[int(s[ind])-96]->il++;
		return curr->g[int(s[ind])-96];
	}
	curr->g[int(s[ind])-96]=new item;
	curr->g[int(s[ind])-96]->il=1;
	curr->g[int(s[ind]-96)]->l=curr->l+2;
	for(int i=1;i<=26;i++) curr->g[int(s[ind])-96]->g[i]=nullptr;
	pitem pom=curr->g[int(s[ind])-96];
	curr=curr->fail;	
	while(curr!=nullptr){	
		if(ind+1>=(curr->l)+2 and s[ind-(curr->l)-1]==s[ind]) break;
		curr=curr->fail;
	}
	if(curr==nullptr) pom->fail=k2;
	else pom->fail=curr->g[int(s[ind])-96];
	return pom;
}
void rek(pitem curr){
	if(!curr) return;
	k[curr->l].push_back(curr);
	for(int i=1;i<=26;i++) rek(curr->g[i]);
}
void solve(){
	cin>>s;
	k1=new item;
	k2=new item;
	k2->fail=k1,k1->fail=nullptr;
	k1->l=-1,k2->l=0,k1->il=0,k2->il=0;
	for(int i=1;i<=26;i++) k1->g[i]=nullptr,k2->g[i]=nullptr;
	pitem curr=k2;
	for(int i=0;i<s.size();i++) curr=add(i,curr);
	rek(k1),rek(k2);
	ll res=0;
	for(int i=s.size();i>=1;i--){
		for(auto u:k[i]){
			res=max(res,(ll)(u->il)*(ll)(u->l));
			u->fail->il+=u->il;
		}
	}
	cout<<res<<"\n";
}
int main(){
	ios_base::sync_with_stdio(0),cin.tie(0);
	solve();
}

Compilation message

palindrome.cpp: In function 'void solve()':
palindrome.cpp:54:15: warning: comparison of integer expressions of different signedness: 'int' and 'std::__cxx11::basic_string<char>::size_type' {aka 'long unsigned int'} [-Wsign-compare]
   54 |  for(int i=0;i<s.size();i++) curr=add(i,curr);
      |              ~^~~~~~~~~

Subtask #1
8.0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7244 KB Output is correct
2 Correct 4 ms 7364 KB Output is correct
3 Correct 3 ms 7300 KB Output is correct
4 Correct 4 ms 7244 KB Output is correct
5 Correct 4 ms 7244 KB Output is correct
6 Correct 4 ms 7244 KB Output is correct
7 Correct 4 ms 7244 KB Output is correct
8 Correct 4 ms 7244 KB Output is correct
9 Correct 4 ms 7364 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7244 KB Output is correct
12 Correct 4 ms 7244 KB Output is correct
13 Correct 4 ms 7372 KB Output is correct
14 Correct 4 ms 7244 KB Output is correct
15 Correct 4 ms 7320 KB Output is correct
16 Correct 4 ms 7244 KB Output is correct
17 Correct 4 ms 7360 KB Output is correct
18 Correct 4 ms 7244 KB Output is correct
19 Correct 4 ms 7372 KB Output is correct
20 Correct 4 ms 7268 KB Output is correct
21 Correct 4 ms 7372 KB Output is correct
22 Correct 4 ms 7340 KB Output is correct
23 Correct 4 ms 7372 KB Output is correct
24 Correct 4 ms 7372 KB Output is correct
25 Correct 4 ms 7356 KB Output is correct
26 Correct 4 ms 7372 KB Output is correct
27 Correct 4 ms 7372 KB Output is correct
28 Correct 4 ms 7360 KB Output is correct
29 Correct 4 ms 7372 KB Output is correct
30 Correct 4 ms 7372 KB Output is correct
31 Correct 6 ms 7364 KB Output is correct
32 Correct 4 ms 7372 KB Output is correct

Subtask #2
15.0 / 15.0

# Verdict Execution time Memory Grader output
1 Correct 4 ms 7620 KB Output is correct
2 Correct 4 ms 7568 KB Output is correct
3 Correct 4 ms 7628 KB Output is correct
4 Correct 4 ms 7500 KB Output is correct
5 Correct 4 ms 7632 KB Output is correct
6 Correct 4 ms 7620 KB Output is correct
7 Correct 4 ms 7504 KB Output is correct
8 Correct 4 ms 7500 KB Output is correct
9 Correct 4 ms 7492 KB Output is correct
10 Correct 4 ms 7360 KB Output is correct
11 Correct 4 ms 7372 KB Output is correct
12 Correct 4 ms 7488 KB Output is correct

Subtask #3
24.0 / 24.0

# Verdict Execution time Memory Grader output
1 Correct 8 ms 9932 KB Output is correct
2 Correct 8 ms 9988 KB Output is correct
3 Correct 8 ms 10188 KB Output is correct
4 Correct 8 ms 10188 KB Output is correct
5 Correct 8 ms 10060 KB Output is correct
6 Correct 8 ms 9932 KB Output is correct
7 Correct 8 ms 9804 KB Output is correct
8 Correct 4 ms 7372 KB Output is correct
9 Correct 4 ms 7372 KB Output is correct
10 Correct 7 ms 9060 KB Output is correct

Subtask #4
26.0 / 26.0

# Verdict Execution time Memory Grader output
1 Correct 59 ms 34124 KB Output is correct
2 Correct 51 ms 33124 KB Output is correct
3 Correct 46 ms 35648 KB Output is correct
4 Correct 55 ms 34016 KB Output is correct
5 Correct 49 ms 33540 KB Output is correct
6 Correct 38 ms 26220 KB Output is correct
7 Correct 41 ms 28796 KB Output is correct
8 Correct 6 ms 7756 KB Output is correct
9 Correct 15 ms 14028 KB Output is correct
10 Correct 42 ms 29764 KB Output is correct

Subtask #5
27.0 / 27.0

# Verdict Execution time Memory Grader output
1 Correct 159 ms 87756 KB Output is correct
2 Correct 145 ms 83224 KB Output is correct
3 Correct 124 ms 92364 KB Output is correct
4 Correct 129 ms 84772 KB Output is correct
5 Correct 150 ms 87800 KB Output is correct
6 Correct 125 ms 75724 KB Output is correct
7 Correct 116 ms 70824 KB Output is correct
8 Correct 9 ms 8264 KB Output is correct
9 Correct 8 ms 8276 KB Output is correct
10 Correct 112 ms 74024 KB Output is correct
11 Correct 155 ms 87756 KB Output is correct
12 Correct 22 ms 15956 KB Output is correct