oj.uz

답안 #253086

# 제출 시각 아이디 문제 언어 결과 실행 시간 메모리
253086 2020-07-26T21:23:26 Z frodakcin 회문 (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

# 결과 실행 시간 메모리 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

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 38016 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #3
0 / 24.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 21 ms 38528 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #4
0 / 26.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 31 ms 44712 KB Output isn't correct
2 Halted 0 ms 0 KB -

Subtask #5
0 / 27.0

# 결과 실행 시간 메모리 Grader output
1 Incorrect 58 ms 58488 KB Output isn't correct
2 Halted 0 ms 0 KB -