QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716952#9406. TriangleYansuan_HClWA 0ms22252kbC++144.6kb2024-11-06 16:28:222024-11-06 16:28:22

Judging History

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

  • [2024-11-06 16:28:22]
  • 评测
  • 测评结果:WA
  • 用时:0ms
  • 内存:22252kb
  • [2024-11-06 16:28:22]
  • 提交

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]]]]);
	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: 18196kb

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: 22252kb

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
0
0
10
6
10
31
10
3
48
6
7339

result:

wrong answer 4th lines differ - expected: '4', found: '0'