QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#400613#5440. P-P-Palindromecomeintocalm#WA 3ms30208kbC++201.7kb2024-04-27 14:18:112024-04-27 14:18:11

Judging History

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

  • [2024-04-27 14:18:11]
  • 评测
  • 测评结果:WA
  • 用时:3ms
  • 内存:30208kb
  • [2024-04-27 14:18:11]
  • 提交

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'