QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#690044 | #9406. Triangle | kenkenken | WA | 0ms | 13872kb | C++23 | 5.7kb | 2024-10-30 19:58:58 | 2024-10-30 19:58:58 |
Judging History
answer
#include <bits/stdc++.h>
#define F first
#define S second
#define pb push_back
#define pob pop_back
#define SZ(x) (int)(x.size())
#define all(x) begin(x), end(x)
#ifdef LOCAL
#define HEHE freopen("in.txt", "r", stdin);
#define debug(...) {cerr << #__VA_ARGS__ << " = "; dbg(__VA_ARGS__);}
#else
#define HEHE ios_base::sync_with_stdio(0), cin.tie(0);
#define debug(...) 7122;
#endif
using namespace std;
#define chmax(a, b) (a) = (a) > (b) ? (a) : (b)
#define chmin(a, b) (a) = (a) < (b) ? (a) : (b)
#define FOR(i, a, b) for (int i = (a); i <= (b); i++)
void dbg() { cerr << '\n'; }
template<typename T, typename ...U>
void dbg(T t, U ...u) { cerr << t << ' '; dbg(u...); }
#define int long long
const int MAXN = 6e5 + 5;
struct suffix_array{
int n, sa[MAXN], nsa[MAXN], cnt[MAXN], tmp[MAXN];
int rk[MAXN], lcp[MAXN];
string s;
void init(string _s) {
s = _s + "$";
n = s.size();
iota(sa, sa + n, 0);
}
void countsort(int sz) {
FOR (i, 0, n - 1) tmp[cnt[i]]++;
FOR (i, 1, sz - 1) tmp[i] += tmp[i - 1];
for (int i = n - 1; i >= 0; i--)
nsa[--tmp[cnt[sa[i]]]] = sa[i];
fill(tmp, tmp + sz, 0);
copy(nsa, nsa + n, sa);
}
void build_SA() {
FOR (i, 0, n - 1) cnt[i] = s[i];
countsort(128);
cnt[sa[0]] = 0;
FOR (i, 1, n - 1) cnt[sa[i]] = cnt[sa[i - 1]] + (s[sa[i]] != s[sa[i - 1]]);
for (int k = 1; k < n; k <<= 1) {
int sz = cnt[sa[n - 1]] + 1;
FOR (i, 0, n - 1)
sa[i] = sa[i] >= k ? sa[i] - k : sa[i] - k + n;
countsort(sz);
tmp[sa[0]] = 0;
FOR (i, 1, n - 1) tmp[sa[i]] = tmp[sa[i - 1]] +
((cnt[sa[i]] != cnt[sa[i - 1]]) or (cnt[(sa[i] + k) % n] != cnt[(sa[i - 1] + k) % n]));
copy(tmp, tmp + n, cnt);
fill(tmp, tmp + n, 0);
}
}
vector<vector<int>> st;
void build_lcp() {
FOR (i, 0, n - 1) rk[sa[i]] = i;
int curlcp = 0;
FOR (i, 0, n - 2) {
while (s[i + curlcp] == s[sa[rk[i] - 1] + curlcp])
curlcp++;
lcp[rk[i]] = curlcp;
curlcp && curlcp--;
}
st.assign(n, vector<int>(19, 0));
FOR (i, 1, n - 1) st[i][0] = lcp[i];
FOR (j, 1, 18) {
for (int i = 1; i + (1 << j) <= n; i++) {
st[i][j] = min(st[i][j - 1], st[i + (1 << (j - 1))][j - 1]);
}
}
}
int _lg(int x) {
return 64 - __builtin_clzll(x) - 1;
}
int LCP(int i, int j) { // [i, j]
if (i > j) swap(i, j);
if (i == j) return n - sa[i];
chmin(j, n - 1); chmax(i, 0);
// min (lcp[i + 1 : j])
i++; j++;
// lcp[i, j)
int lg = _lg(j - i);
return min(st[i][lg], st[j - (1 << lg)][lg]);
}
void solve(int _n, vector<string> _s, vector<int> pos) {
// FOR (i, 0, n - 1) {
// cout << i << ' ' << s.substr(sa[i]) << '\n';
// }
int maxlen = 0;
FOR (i, 0, _n - 1) chmax(maxlen, _s[i].size());
vector<int> a;
vector<vector<int>> a1(maxlen + 1);
FOR (i, 0, _n - 1) {
a1[SZ(_s[i])].pb(rk[pos[i]]);
a.pb(rk[pos[i]]);
}
sort(all(a));
FOR (i, 0, maxlen) sort(all(a1[i]));
map<string, int> sum;
map<int, int> ap;
map<string, int> ctt;
FOR (i, 0, _n - 1) ctt[_s[i]]++;
FOR (i, 0, _n - 1) ap[i] = ctt[_s[i]];
int ans = 0;
FOR (i, 0, _n - 1) {
int sum2 = 0;
FOR (len, 1, SZ(_s[i]) - 1) {
// _s[i] [1: len]
int l = rk[pos[i]], r = rk[pos[i]];
for (int j = 18; j >= 0; j--) {
if (l >= (1 << j) and LCP(l - (1 << j), rk[pos[i]]) >= len) {
l -= 1 << j;
}
}
int sb = upper_bound(all(a1[len]), r) - lower_bound(all(a1[len]), l);
int l1 = rk[pos[i] + len], r1 = rk[pos[i]];
for (int j = 18; j >= 0; j--) {
if (l1 + (1 << j) < n and LCP(rk[pos[i] + len], l1 + (1 << j)) >= SZ(_s[i]) + 1 - len) {
l1 += 1 << j;
}
} l1++;
int overlap = 0;
int sc = max(0ll, (int)(upper_bound(all(a), r1) - a.begin()) - (lower_bound(all(a), l1) - a.begin()));
if (sc == 0) overlap = 0;
else if (l1 < l) overlap = sb;
else if (l1 > r) overlap = 0;
else upper_bound(all(a1[len]), r) - lower_bound(all(a1[len]), l1);
ans += sb * sc - overlap;
sum2 += sb;
if (sb * sc - overlap != 0) {
//debug(_s[i], len, sb, sc, overlap);
}
}
sum[_s[i]] = sum2;
}
map<string, int> mp;
for (string tmp : _s) {
mp[tmp]++;
}
//cout << ans << '\n';
int ct = 0;
for (auto [x, y] : mp) {
ans += y * (y - 1) / 2 * ct;
ans += y * (y - 1) * (y - 2) / 6;
ct += y;
}
cout << ans << '\n';
}
} SA;
void solve() {
int n; cin >> n;
vector<string> s(n);
for (auto &i : s) cin >> i;
sort(all(s));
vector<int> pos(n);
string tmp;
FOR (i, 0, n - 1) {
pos[i] = tmp.size();
tmp += s[i];
if (i != n - 1) tmp += "$";
}
SA.init(tmp);
SA.build_SA();
SA.build_lcp();
SA.solve(n, s, pos);
}
signed main() {
HEHE
int t; cin >> t;
while (t--) solve();
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 0
Wrong Answer
time: 0ms
memory: 13872kb
input:
3 6 cbaa cb cb cbaa ba ba 3 sdcpc sd cpc 1 ccpc
output:
24 1 0
result:
wrong answer 1st lines differ - expected: '16', found: '24'