QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#140962 | #5440. P-P-Palindrome | mendicillin2 | WA | 1ms | 3576kb | C++14 | 2.1kb | 2023-08-17 01:59:20 | 2023-08-17 01:59:23 |
Judging History
answer
#include <bits/stdc++.h>
using namespace std;
#define rep(i, a, b) for (int i = int(a); i < int(b); i++)
#define trav(a, x) for (auto& a : x)
#define per(i, a, b) for (int i = int(b) - 1; i >= int(a); i--)
#define sz(x) int(x.size())
#define all(x) x.begin(), x.end()
template <class T> using vc = vector<T>;
template <class T> using vvc = vc<vc<T>>;
using ll = int64_t;
using vi = vc<int>;
using pii = pair<int, int>;
// Author: maroonrk (modified)
// https://codeforces.com/contest/1738/submission/174140231
template<class S>
struct eertree{
struct N{
int suf,ser,l,r;
int len(){return r-l;}
map<int,int> ch;
//array<int,26> ch;
};
vc<N> x;
int dist(int v){
if(x[v].suf<=0)return -1;
return x[v].len()-x[x[v].suf].len();
}
int c;
S s;
eertree(){
x.push_back({-1,-1,1,0,{}});
x.push_back({0,-1,0,0,{}});
c=1;
}
void reserve(int n) {
s.reserve(n+5);
x.reserve(n+5);
}
bool chk(int v,int i){
int l=i-x[v].len();
return l>0&&s[l-1]==s[i];
}
template<class t>
int extend(t z){
int i=sz(s);
s.push_back(z);
while(!chk(c,i))c=x[c].suf;
if(x[c].ch.count(s[i])==0){
int d=x[c].suf;
if(d!=-1)while(!chk(d,i))d=x[d].suf;
int e=d==-1?1:x[d].ch[s[i]];
int f=x[c].ch[s[i]]=sz(x);
x.push_back({e,e,i-x[c].len()-1,i+1,{}});
if(dist(f)==dist(e))
x[f].ser=x[e].ser;
}
return c=x[c].ch[s[i]];
}
N& operator[](int i){
return x[i];
}
};
int main() {
ios_base::sync_with_stdio(false), cin.tie(nullptr);
cout << fixed << setprecision(20);
int N;
cin >> N;
eertree<vector<int>> et;
const int MAX = 3e6;
et.reserve(MAX);
for (int i = 0; i < N; i++) {
string s;
cin >> s;
const int L = int(s.size());
for (int j = 0; j < L; j++) {
int x = int(s[j] - 'a');
et.extend(x);
}
et.extend(26 + 2*i);
et.extend(26 + 2*i+1);
}
ll ans = 0;
const int num = int(et.x.size());
for (int v = 2; v < num; v++) {
if (et[v].suf == et[v].ser) {
ans++;
} else {
int period = et.dist(v);
int len = et[v].len();
ans += 2 * (len / period) - 1;
}
}
ans -= 2*N;
cout << ans << '\n';
}
詳細信息
Test #1:
score: 100
Accepted
time: 1ms
memory: 3576kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 1ms
memory: 3544kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 1ms
memory: 3528kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 3500kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1332
result:
wrong answer 1st numbers differ - expected: '1282', found: '1332'