oj.uz

Submission #253086

# Submission time Handle Problem Language Result Execution time Memory
253086 2020-07-26T21:23:26 Z frodakcin Palindromes (APIO14_palindrome) C++11
0 / 100
 58 ms 58488 KB 
#include <cstdio>
#include <cstring>
#include <cassert>
#include <vector>

template<typename T> bool ckmax(T& a, const T& b) {return a<b?a=b,1:0;}

const int MN = 3e5+10;
const int MK = 26;

typedef long long ll;

int N, c[MN][MK], l[MN], d[MN], p, X=1, v[MN];
ll f;
std::vector<int> dw[MN];
char s[MN];
void dfs(int n)
{
	s[n]=1;
	for(auto x:dw[n])
		dfs(x), s[n]+=s[x];
	ckmax(f, (ll)s[n]*d[n]);
}
int main()
{
	scanf(" %s", s+1);
	for(N=1;s[N];++N)s[N]-='a';
	s[0]=-1, s[N--]=-2;
	memset(c, -1, sizeof c);
	d[0]=l[0]=-1, d[1]=l[1]=0;
	dw[0].push_back(1);
	for(int i=1;i<=N;++i)
	{
		for(;s[i]!=s[i-d[p]-1];)p=l[p];
		if(!~c[p][s[i]])
		{
			c[p][s[i]]=++X;
			d[X]=d[p]+2, l[X]=l[p];
			p=X;
			for(;~l[p] && s[i]!=s[i-d[l[p]]-1];l[p]=l[l[p]]);
			if(~l[p] && s[i]==s[i-d[l[p]]-1])
				l[p]=c[l[p]][s[i]];
			else
				l[p]=1;
			assert(~l[p]);
			dw[l[p]].push_back(p);
		}
		else
			p=c[p][s[i]];
		++v[p];
	}
	dfs(0);
	printf("%lld\n", f);
	return 0;
}

Compilation message

palindrome.cpp: In function 'int main()':
palindrome.cpp:35:17: warning: array subscript has type 'char' [-Wchar-subscripts]
   if(!~c[p][s[i]])
                 ^
palindrome.cpp:37:13: warning: array subscript has type 'char' [-Wchar-subscripts]
    c[p][s[i]]=++X;
             ^
palindrome.cpp:42:22: warning: array subscript has type 'char' [-Wchar-subscripts]
     l[p]=c[l[p]][s[i]];
                      ^
palindrome.cpp:49:15: warning: array subscript has type 'char' [-Wchar-subscripts]
    p=c[p][s[i]];
               ^
palindrome.cpp:26:7: warning: ignoring return value of 'int scanf(const char*, ...)', declared with attribute warn_unused_result [-Wunused-result]
  scanf(" %s", s+1);
  ~~~~~^~~~~~~~~~~~

Subtask #1
0 / 8.0

# Verdict Execution time Memory Grader output
1 Correct 19 ms 37888 KB Output is correct
2 Correct 18 ms 37888 KB Output is correct
3 Correct 19 ms 37888 KB Output is correct
4 Correct 18 ms 37888 KB Output is correct
5 Correct 19 ms 37888 KB Output is correct
6 Correct 20 ms 37888 KB Output is correct
7 Correct 18 ms 37888 KB Output is correct
8 Correct 20 ms 37888 KB Output is correct
9 Correct 18 ms 37888 KB Output is correct
10 Correct 20 ms 37888 KB Output is correct
11 Correct 20 ms 37888 KB Output is correct
12 Correct 19 ms 37888 KB Output is correct
13 Correct 19 ms 37888 KB Output is correct
14 Incorrect 19 ms 37888 KB Output isn't correct
15 Halted 0 ms 0 KB -

Subtask #2
0 / 15.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# Verdict Execution time Memory Grader output
1 Incorrect 21 ms 38528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# Verdict Execution time Memory Grader output
1 Incorrect 31 ms 44712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# Verdict Execution time Memory Grader output
1 Incorrect 58 ms 58488 KB Output isn't correct
2 Halted 0 ms 0 KB -