QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#400613 | #5440. P-P-Palindrome | comeintocalm# | WA | 3ms | 30208kb | C++20 | 1.7kb | 2024-04-27 14:18:11 | 2024-04-27 14:18:11 |
Judging History
answer
#include <bits/stdc++.h>
const int N = 1e6 + 5;
long long ans;
struct PAM {
struct node {
int next[26];
int suf, len;
} t[N];
int tot, suff;
std::vector<int> ver[N];
int max[N];
PAM() {
tot = 2, suff = 1;
t[1].len = -1, t[1].suf = 1;
t[2].len = 0, t[2].suf = 1;
ver[1].emplace_back(2);
}
void init() {
suff = 1;
}
void insert(std::string &s, int pos) {
int cur = suff, k = s[pos] - 'a';
for (; s[pos - 1 - t[cur].len] != s[pos]; cur = t[cur].suf);
if (t[cur].next[k]) {
suff = t[cur].next[k];
return ;
}
suff = ++tot;
t[cur].next[k] = tot;
t[tot].len = t[cur].len + 2;
max[tot] = 1;
if (t[tot].len == 1) {
t[tot].suf = 2;
ver[t[tot].suf].emplace_back(tot);
return ;
}
cur = t[cur].suf;
for (; s[pos - 1 - t[cur].len] != s[pos]; cur = t[cur].suf);
t[tot].suf = t[cur].next[k];
ver[t[tot].suf].emplace_back(tot);
}
void dfs(const int u) {
for (auto &&v : ver[u]) {
dfs(v);
}
if (t[u].len > 0) {
if (t[t[u].suf].len * 2 < t[u].len) {
// std::cout << u << ' ' << max[u] << '\n';
ans += 1ll * max[u] * max[u];
} else {
max[t[u].suf] = std::max(max[u], t[u].len / (t[u].len - t[t[u].suf].len));
}
}
}
} pam;
int main() {
std::cin.tie(0)->sync_with_stdio(0);
int n;
std::cin >> n;
for (int i = 1; i <= n; ++i) {
std::string s;
std::cin >> s;
pam.init();
for (int pos = 0; pos < s.length(); ++pos) {
pam.insert(s, pos);
}
}
pam.dfs(1);
std::cout << ans << '\n';
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 3ms
memory: 28200kb
input:
2 aaaa aaa
output:
16
result:
ok 1 number(s): "16"
Test #2:
score: 0
Accepted
time: 0ms
memory: 30208kb
input:
3 abaaa abbbba bbbaba
output:
28
result:
ok 1 number(s): "28"
Test #3:
score: 0
Accepted
time: 0ms
memory: 28388kb
input:
1 aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaab
output:
15130
result:
ok 1 number(s): "15130"
Test #4:
score: -100
Wrong Answer
time: 0ms
memory: 28444kb
input:
3 aaaaaaaaaaaaaaaaaaaaaaaaa bbbbbbbbbbbbbbbbbbbbbbbbb bababababababaabababababa
output:
1295
result:
wrong answer 1st numbers differ - expected: '1282', found: '1295'