QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398586#5440. P-P-PalindromecwfxlhWA 12ms108592kbC++141.5kb2024-04-25 15:26:032024-04-25 15:26:04

Judging History

你现在查看的是最新测评结果

  • [2024-04-25 15:26:04]
  • 评测
  • 测评结果:WA
  • 用时:12ms
  • 内存:108592kb
  • [2024-04-25 15:26:03]
  • 提交

answer

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n,lst,k1,k2,k3,k4,k5,k6,k7,k8,k9,wz,flg;
ll ans;
string S[1000003];
struct PAM{
	int fa;
	int tr[27];
	int len;
}P[3000003];
int totP,val[3000003];
vector<int>E[3000003];
void dfs(int now){
	if(now!=1&&now!=2){
		ans+=val[P[now].len-P[P[now].fa].len];
		val[P[now].len-P[P[now].fa].len]++;
	}
	for(auto i:E[now])dfs(i);
	if(now!=1&&now!=2)val[P[now].len-P[P[now].fa].len]--;
	return;
}
int main(){
	ios::sync_with_stdio(false);
	cin>>n;
	for(int i=1;i<=n;i++)cin>>S[i];
	P[totP=1].len=-1;
	P[totP=2].len=0;
	P[2].fa=1;
	for(int i=1;i<=n;i++){
		lst=2;
		for(int j=0;j<S[i].length();j++){
			k1=lst;
			flg=1;
			while(k1){
				if(j-P[k1].len-1>=0&&S[i][j]==S[i][j-P[k1].len-1]){
					if(P[k1].tr[S[i][j]-'a'+1]==0){
						P[k1].tr[S[i][j]-'a'+1]=++totP;
						P[totP].len=P[k1].len+2;
						P[totP].fa=k1;
						if(P[totP].len==1){
							P[totP].fa=2;
							flg=0;
						}
						else P[totP].fa=P[k1].fa;
						lst=totP;
					}
					else{
						flg=0;
						lst=P[k1].tr[S[i][j]-'a'+1];
					}
					break;
				}
				k1=P[k1].fa;
			}
			if(!flg)continue;
			while(P[totP].fa){
				if(j-P[P[totP].fa].len-1>=0&&S[i][j]==S[i][j-P[P[totP].fa].len-1]){
					P[totP].fa=P[P[totP].fa].tr[S[i][j]-'a'+1];
					break;
				}
				P[totP].fa=P[P[totP].fa].fa;
			}
		}
	}
	for(int i=1;i<=totP;i++)if(P[i].fa)E[P[i].fa].emplace_back(i);
	dfs(1);
	ans*=2ll;
	ans+=(totP-2);
	cout<<ans;
	return 0;
}

详细

Test #1:

score: 100
Accepted
time: 7ms
memory: 108528kb

input:

2
aaaa
aaa

output:

16

result:

ok 1 number(s): "16"

Test #2:

score: 0
Accepted
time: 12ms
memory: 108568kb

input:

3
abaaa
abbbba
bbbaba

output:

28

result:

ok 1 number(s): "28"

Test #3:

score: 0
Accepted
time: 12ms
memory: 108556kb

input:

1
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab

output:

15130

result:

ok 1 number(s): "15130"

Test #4:

score: -100
Wrong Answer
time: 11ms
memory: 108592kb

input:

3
aaaaaaaaaaaaaaaaaaaaaaaaa
bbbbbbbbbbbbbbbbbbbbbbbbb
bababababababaabababababa

output:

1332

result:

wrong answer 1st numbers differ - expected: '1282', found: '1332'