QOJ.ac

QOJ

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#716963#9406. TrianglePurslaneRE 3ms44736kbC++143.8kb2024-11-06 16:30:542024-11-06 16:30:54

Judging History

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

  • [2024-11-06 16:30:54]
  • 评测
  • 测评结果:RE
  • 用时:3ms
  • 内存:44736kb
  • [2024-11-06 16:30:54]
  • 提交

answer

#include<bits/stdc++.h>
#define int long long
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=3e5+10,MOD=998244353;
int T,n,tot,tr[MAXN][27],fa[MAXN],str[MAXN],rev[MAXN],sze[MAXN],son[MAXN],ds,dfn[MAXN],pre[MAXN],top[MAXN];
int dep[MAXN],hval[MAXN],pw[MAXN];
string rd[MAXN]; int psl[MAXN];
vector<int> HVAL[MAXN],NXT[MAXN];
void init(void) {
	ffor(i,1,tot) HVAL[i].clear(),NXT[i].clear(),psl[i]=0,memset(tr[i],0,sizeof(tr[i])),str[i]=0;
	ds=0,tot=1;
	return ;
}
void insert(string S,int pslid) {
	int u=1;
	for(auto ch:S) {
		if(!tr[u][ch-'a']) tr[u][ch-'a']=++tot,fa[tot]=u;
		u=tr[u][ch-'a'];
	}
	str[u]++,psl[u]=pslid;
	return ;
}
void Init(void) {
	pw[0]=1;
	ffor(i,1,tot) pw[i]=pw[i-1]*26%MOD;	
	return ;
}
void dfs1(int u) {
	sze[u]=1,son[u]=0,dfn[u]=++ds,rev[ds]=u;
	ffor(i,0,25) if(tr[u][i]) {
		dep[tr[u][i]]=dep[u]+1,dfs1(tr[u][i]),sze[u]+=sze[tr[u][i]];
		if(sze[tr[u][i]]>sze[son[u]]) son[u]=tr[u][i];
	}
	return ;
}
void dfs2(int u) {
	HVAL[top[u]].push_back(hval[u]),NXT[top[u]].push_back(u);
	ffor(i,0,25) if(tr[u][i]) {
		if(tr[u][i]==son[u]) top[tr[u][i]]=top[u],hval[tr[u][i]]=(hval[u]*26+i)%MOD;
		else top[tr[u][i]]=tr[u][i],hval[u]=0;
		dfs2(tr[u][i]);
	}
	return ;
}
int len,col[MAXN],Hval[MAXN];
int get_match(int u,int pos) {
	if(pos==len+1) return u;
	if(tr[u][col[pos]]==0) return u;
	if(tr[u][col[pos]]) return get_match(tr[u][col[pos]],pos+1);
	int ans=-1,l=1,r=min(len-pos+1,(int)NXT[top[u]].size()-1-(dep[u]-dep[top[u]]));
	while(l<=r) {
		int mid=l+r>>1;
		if(((Hval[pos+mid-1]-Hval[pos-1]*pw[mid])%MOD+MOD)%MOD==((HVAL[u][dep[u]-dep[top[u]]+mid]-HVAL[u][dep[u]-dep[top[u]]]*pw[mid])%MOD+MOD)%MOD) ans=mid,l=mid+1;
		else r=mid-1;
	}
	return get_match(NXT[u][dep[u]-dep[top[u]]+ans],pos+ans);
}
int get_dfn(int pos) {
	int u=get_match(1,pos);
	if(dep[u]-dep[1]==len-pos+1) return dfn[u];
	int nxt=pos+dep[u]-dep[1];
	roff(j,25,0) if(j<col[nxt]&&tr[u][j]) return dfn[tr[u][j]]+sze[tr[u][j]]-1;
	return dfn[u];
}
namespace DS {
	int tr[MAXN];
	void init(void) {
		ffor(i,1,tot) tr[i]=0;
		return ;		
	}
	void update(int pos,int v) {
		while(pos<=tot) tr[pos]+=v,pos+=pos&-pos;
		return ;
	}
	int query(int pos) {
		int ans=0;
		while(pos) ans+=tr[pos],pos-=pos&-pos;
		return ans;	
	}
}
signed main() {
	ios::sync_with_stdio(false),cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--) {
		init();
		cin>>n;
		ffor(i,1,n) cin>>rd[i],insert(rd[i],i);	
		DS::init(),Init();
		dfs1(1),top[1]=1,dfs2(1);
		ffor(i,1,tot) pre[i]=str[rev[i]]+pre[i-1];
		int ans=0;
		roff(j,tot,1) {
			int i=rev[j];
			if(str[i]) {
				len=dep[i]-dep[1];
				int u=i,id=psl[i];
				ffor(k,1,len) col[k]=rd[id][k-1]-'a',Hval[k]=(Hval[k-1]*26+rd[id][k-1]-'a')%MOD;
				map<int,vector<pair<int,int>>> mp;
				ffor(k,1,len) {
					int lim=get_dfn(len-k+2);
					//必须 > lim
					if(k!=1&&lim<j) {
						ans+=(pre[j-1]-pre[lim])*str[u]*str[i];
						if(dfn[u]>lim) ans+=str[u]*(str[u]-1)/2*str[i];
						mp[lim+1].push_back({dfn[u],str[u]});
						mp[dfn[u]].push_back({-lim-1,str[u]});
					}
					u=fa[u];
				}
				auto it=--mp.end();
				while(1) {
					auto vc=it->second;
					sort(vc.begin(),vc.end());
					for(auto pr:vc) {
						if(pr.first<0) DS::update(-pr.first,pr.second);
						else ans-=DS::query(pr.first)*pr.second*str[i];
					}
					if(it==mp.begin()) break ;
					it--;	
				}
				it=--mp.end();
				while(1) {
					auto vc=it->second;
					sort(vc.begin(),vc.end());
					for(auto pr:vc) {
						if(pr.first<0) DS::update(-pr.first,-pr.second);
					}
					if(it==mp.begin()) break ;
					it--;	
				}
				ans+=str[i]*(str[i]-1)/2*pre[j-1]+str[i]*(str[i]-1)*(str[i]-2)/6;
				
			}
		}
		cout<<ans<<'\n';
	}
	return 0;
}

詳細信息

Test #1:

score: 100
Accepted
time: 3ms
memory: 44736kb

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
Runtime Error

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:


result: