QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#716957 | #9406. Triangle | Yansuan_HCl | WA | 0ms | 22236kb | C++14 | 4.7kb | 2024-11-06 16:29:11 | 2024-11-06 16:29:12 |
Judging History
answer
#include <bits/stdc++.h>
#define ms(x, v) memset(x, v, sizeof(x))
#define il __attribute__((always_inline)) static
#define U(i,l,r) for(int i(l),END##i(r);i<=END##i;++i)
#define D(i,r,l) for(int i(r),END##i(l);i>=END##i;--i)
using namespace std;
using ll = long long;
#define IC isdigit(c)
#define GC c=getchar()
void rd(auto &x) { x = 0; char GC; bool f = 0;
for (; !IC; GC) f |= c == '-';
for (; IC; GC) x = x * 10 + c - 48;
if (f) x = -x;
}
void rd(auto &x, auto &...y) { rd(x); rd(y...); }
#define meow(...) fprintf(stderr, __VA_ARGS__)
#define Assert(e, v) if (!(e)) { meow("AF@%d\n", __LINE__ ); exit(v); }
#define vc vector
#define eb emplace_back
#define pb push_back
const int N = 300005;
int n, m, max_l; char s[N];
int beg[N], ter[N], lim[N]; // [beg,ter)
bool tag[N];
int sa[N], rk[N]; // , hei[N];
void build_sa() {
U (i, 1, m) sa[i] = i, rk[i] = s[i] - 'a' + 1;
// clog << "*********";
// U (i, 1, m)
// clog << sa[i] << ' ';
// clog << endl;
int p = 26;
U (k, 0, max(1, __lg(max_l))) {
int w = 1 << k;
int cnt[p + 1] {}, id[m + 1]; memcpy(id, sa, sizeof(int) * (m + 1));
U (i, 1, m) {
int u = id[i], v = u + w >= lim[u] ? 0 : rk[u + w];
++cnt[v];
}
U (i, 1, p) cnt[i] += cnt[i - 1];
D (i, m, 1) {
int u = id[i], v = u + w >= lim[u] ? 0 : rk[u + w];
sa[cnt[v]--] = u;
}
// clog << "*********";
// U (i, 1, m)
// clog << sa[i] << ' ';
// clog << endl;
ms(cnt, 0);
memcpy(id, sa, sizeof(int) * (m + 1));
U (i, 1, m) {
++cnt[rk[sa[i]]];
}
U (i, 1, p) cnt[i] += cnt[i - 1];
D (i, m, 1) {
sa[cnt[rk[id[i]]]--] = id[i];
}
// clog << "*********";
// U (i, 1, m)
// clog << sa[i] << ' ';
// clog << endl;
memcpy(id, rk, sizeof(int) * (m + 1));
const int *ork = id;
p = 0;
U (i, 1, m) {
if (ork[sa[i]] != ork[sa[i - 1]]
|| ((sa[i] + w >= lim[sa[i]]) ^ (sa[i - 1] + w >= lim[sa[i - 1]]))
|| (sa[i] + w < lim[sa[i]] && ork[sa[i] + w] != ork[sa[i - 1] + w]))
++p;
rk[sa[i]] = p;
}
// meow("gg");
}
// clog << "*********";
// U (i, 1, m)
// clog << sa[i] << ' ';
// clog << endl;
// int k = 0;
// U (i, 1, m) {
// assert(rk[i]);
// assert(k);
// if (k) --k;
// while (i + k < lim[i] && sa[rk[i] - 1] + k < lim[sa[rk[i] - 1]] && s[i + k] == s[sa[rk[i] - 1] + k])
// ++k;
// hei[0][rk[i]] = k;
// }
// U (k, 1, __lg(m)) U (i, 1, m - (1 << k) + 1)
// hei[k][i] = min(hei[k - 1][i], hei[k - 1][i + (1 << k - 1)]);
}
//int lcp(int l, int r) {
// ++l; int g = __lg(r - l + 1);
// return min(hei[g][l], hei[g][r - (1 << g) + 1]);
//}
int ch[N][26] {}, tp; vc<int> hok[N];
void insert(int l, int r, int id) {
int p = 0;
U (i, l, r - 1) {
int c = s[i] - 'a' + 1;
if (!ch[p][c]) ch[p][c] = ++tp;
p = ch[p][c];
}
hok[p].pb(id);
}
int stk[N], sp, sum[N]; ll ans;
void dfs(int p) {
for (int c : hok[p]) {
for (int i = 1, j; i <= sp; i = j) {
j = i; while (j <= sp && rk[beg[stk[j]]] == rk[beg[stk[i]]]) ++j;
int b = stk[i];
int x = ter[b] - beg[b] == ter[c] - beg[c] ? 1 : rk[beg[c] + ter[b] - beg[b]] + 1,
y = rk[beg[b]];
if (x < y)
ans += (j - i) * (sum[x] - sum[y]);
if (x <= y)
ans += (j - i) * (j - i - 1) / 2;
}
}
ll t = hok[p].size();
if (t) {
ans += t * (t - 1) / 2 * (sum[1] - sum[rk[beg[hok[p][0]]]]);
ans += t * (t - 1) * (t - 2) / 6;
}
for (int c : hok[p])
stk[++sp] = c;
U (c, 0, 25) if (ch[p][c])
dfs(ch[p][c]);
sp -= hok[p].size();
}
void solve() {
rd(n);
ter[0] = 1;
U (i, 1, n) {
beg[i] = ter[i - 1];
scanf("%s", s + beg[i]);
ter[i] = beg[i] + strlen(s + beg[i]);
U (j, beg[i], ter[i] - 1) lim[j] = ter[i];
tag[beg[i]] = 1;
// len[beg[i]] = ter[i] - beg[i];
insert(beg[i], ter[i], i);
max_l = max(max_l, ter[i] - beg[i]);
}
m = ter[n] - 1;
// U (i, 1, m) clog << s[i];
// clog << endl;
build_sa();
// U (i, 1, m) clog << rk[i] << ' ';
// clog << endl;
U (i, 1, n) {
++sum[rk[beg[i]]];
// clog << "#" << rk[beg[i]] << endl;
}
// clog << "!" << m << endl;
D (i, m, 0) sum[i] += sum[i + 1];
// U (i, 1, m) pre[i] = rk[sa[i]] == rk[sa[i - 1]] ? pre[i - 1] : i;
dfs(0);
printf("%lld\n", ans);
}
void clear() {
memset(s, 0, sizeof(char) * (m + 1));
memset(beg, 0, sizeof(int) * (n + 1));
memset(ter, 0, sizeof(int) * (n + 1));
memset(lim, 0, sizeof(int) * (m + 1));
memset(tag, 0, sizeof(bool) * (m + 1));
memset(ch, 0, sizeof(int[26]) * (tp + 1));
memset(sum, 0, sizeof(int) * (m + 2));
U (i, 1, tp) hok[i].clear();
ans = 0;
max_l = 0;
m = 0;
}
int main() {
// freopen("ava.in", "r", stdin);
int T; rd(T);
while (T--) {
solve();
clear();
}
}
詳細信息
Test #1:
score: 100
Accepted
time: 0ms
memory: 22236kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
16 0 0
result:
ok 3 lines
Test #2:
score: -100
Wrong Answer
time: 0ms
memory: 18304kb
input:
14 1 lfpbavjsm 2 pdtlkfwn mbd 3 dvqksg dvqksg uhbhpyhj 4 ombwb ombwb ombwb ombwb 5 oztclz oztclz oztclz oztclz kul 6 vco vco vco dtktsqtinm vco vco 7 tb tb kowbsu ygkfphcij tb uvei tb 8 vxxtxssht abnsxbf bydaae bydaae udalyvmcef bydaae bydaae bydaae 9 aaze zvyonw qjfv mmhkef qjfv qjfv qjfv mmhkef qj...
output:
0 0 0 4 0 20 10 20 41 14 3 52 7 9189
result:
wrong answer 5th lines differ - expected: '10', found: '0'