QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#398586 | #5440. P-P-Palindrome | cwfxlh | WA | 12ms | 108592kb | C++14 | 1.5kb | 2024-04-25 15:26:03 | 2024-04-25 15:26:04 |
Judging History
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'