QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#398412#5440. P-P-PalindromecaijianhongCompile Error//C++141.9kb2024-04-25 11:48:012024-04-25 11:48:01

Judging History

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

  • [2024-04-25 11:48:01]
  • 评测
  • [2024-04-25 11:48:01]
  • 提交

answer

// 
#include <bits/stdc++.h>
using namespace std;
#ifdef LOCAL
#define debug(...) fprintf(stderr, ##__VA_ARGS__)
#else
#define endl "\n"
#define debug(...) void(0)
#endif
typedef long long LL;
template <int N>
struct palindam {
  unordered_map<int, int> ch[N + 10];
  int fail[N + 10], len[N + 10], dif[N + 10], tot, trans[N + 10];
  palindam() : tot(1) { fail[0] = 1, len[1] = -1; }
  int getfail(int p, char* s, int rlen) {
    while (len[p] + 1 >= rlen || s[0] != s[-len[p] - 1]) p = fail[p];
    return p;
  }
  int expand(int p, int r, char* s, int rlen) {
    p = getfail(p, s, rlen);
    if (ch[p][r]) return ch[p][r];
    int u = ++tot;
    len[u] = len[p] + 2;
    fail[u] = ch[getfail(fail[p], s, rlen)][r];
    dif[u] = len[u] - len[fail[u]];
    return ch[p][r] = u;
  }
};
int n;
palindam<1000010> M;
vector<int> g[1000010];
pair<int, int> stk[1000010];
int top, cnt[1000010];
void dfs(int u) {
  stk[++top] = make_pair(M.len[u], u);
  if (u > 1 && M.len[u] % M.dif[u] == 0) {
    auto [l, f] = *lower_bound(stk + 1, stk + top + 1, make_pair(M.dif[u], 0));
    debug("u = %d, len = %d, dif = %d, find f = %d, f.l = %d\n", u, M.len[u], M.dif[u], f, l);
    cnt[lower_bound(stk + 1, stk + top + 1, make_pair(M.dif[u], 0))->second] += 1;
  } else {
    cnt[u] += 1;
  }
  for (int v : g[u]) dfs(v);
  --top;
}
int main() {
#ifndef LOCAL
  cin.tie(nullptr)->sync_with_stdio(false);  
#endif
  cin >> n;
  for (int i = 1; i <= n; i++) {
    string s;
    cin >> s;
    for (int j = 0, lst = 1; j < (int)s.size(); j++)
      lst = M.expand(lst, s[j] - 'a', s.data() + j, j + 1);
  }
  for (int i = 0; i <= M.tot; i++) for (auto [r, v] : M.ch[i]) debug("%d %d %c\n", i, v, r + 'a');
  for (int i = 2; i <= M.tot; i++) g[M.fail[i]].push_back(i);
  dfs(0);
  LL ans = 0;
  for (int i = 2; i <= M.tot; i++) ans += 1ll * cnt[i] * cnt[i];
  cout << ans << endl;
  return 0;
}

詳細信息

answer.code: In function ‘void dfs(int)’:
answer.code:38:10: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   38 |     auto [l, f] = *lower_bound(stk + 1, stk + top + 1, make_pair(M.dif[u], 0));
      |          ^
answer.code: In function ‘int main()’:
answer.code:56:48: error: invalid conversion from ‘const char*’ to ‘char*’ [-fpermissive]
   56 |       lst = M.expand(lst, s[j] - 'a', s.data() + j, j + 1);
      |                                       ~~~~~~~~~^~~
      |                                                |
      |                                                const char*
answer.code:20:34: note:   initializing argument 3 of ‘int palindam<N>::expand(int, int, char*, int) [with int N = 1000010]’
   20 |   int expand(int p, int r, char* s, int rlen) {
      |                            ~~~~~~^
answer.code:58:46: warning: structured bindings only available with ‘-std=c++17’ or ‘-std=gnu++17’ [-Wc++17-extensions]
   58 |   for (int i = 0; i <= M.tot; i++) for (auto [r, v] : M.ch[i]) debug("%d %d %c\n", i, v, r + 'a');
      |                                              ^