QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#716683 | #9406. Triangle | Purslane | WA | 6ms | 48836kb | C++14 | 3.3kb | 2024-11-06 15:49:10 | 2024-11-06 15:49:10 |
Judging History
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;
ffor(k,1,len) {
int lim=get_dfn(len-k+2);
DS::update(dfn[u],str[u]);
// cout<<"DEBUG"<<rd[id]<<' '<<len-k+2<<' '<<lim<<'\n';
//必须 > lim
if(k!=1&&lim<j) {
ans+=(pre[j]-pre[lim]-(DS::query(j)-DS::query(lim)))*str[u]*str[i];
if(dfn[u]>lim) ans+=str[u]*(str[u]-1)/2*str[i];
}
u=fa[u];
}
ans+=str[i]*(str[i]-1)/2*pre[j-1]+str[i]*(str[i]-1)*(str[i]-2)/6;
u=i;
ffor(j,1,len) {
DS::update(dfn[u],-str[u]);
u=fa[u];
}
}
}
cout<<ans<<'\n';
}
return 0;
}
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 0ms
memory: 48692kb
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: 0
Accepted
time: 6ms
memory: 48836kb
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 10 20 10 20 41 14 63 74 18 11081
result:
ok 14 lines
Test #3:
score: 0
Accepted
time: 2ms
memory: 44736kb
input:
11 10 bppzfsncq bppzfsncq vcqxgcehdx bppzfsncq bppzfsncq muwrcvt w aanwhqmync aanwhqmync bppzfsncq 10 t jkky t z t t z z z t 10 qidkyca uhqubvbo kosyvh gsj gsj gsj duo jrro gsj jrro 10 lhktb lhktb lhktb uohl lhktb r lhktb lhktb wruim lhktb 10 e gqvdmpvxb gqvdmpvxb gqvdmpvxb sttirbhz gqvdmpvxb zdfpm ...
output:
30 60 15 35 20 20 23 12 38 44 8047
result:
ok 11 lines
Test #4:
score: -100
Wrong Answer
time: 3ms
memory: 45268kb
input:
11 100 kalgqjh mdszzwe qxn kalgqjh hy kalgqjh suplvp r kkeoxmx tcoise suplvp suplvp y kalgqjh vrwniyici jmnyrradyq kalgqjh kalgqjh suplvp rkg xzevyk zc suplvp hcupv kalgqjh qakyahjaoi mum pbg u ip kalgqjh kalgqjh jngc ylr suplvp qxn kalgqjh bzwodm e kalgqjh kalgqjh evmm kbymvbccs kalgqjh suplvp kalg...
output:
12478 6722 9220 6668 4933 11233 7950 5470 4525 5743 1586016
result:
wrong answer 5th lines differ - expected: '4934', found: '4933'