QOJ.ac
QOJ
ID | 题目 | 提交者 | 结果 | 用时 | 内存 | 语言 | 文件大小 | 提交时间 | 测评时间 |
---|---|---|---|---|---|---|---|---|---|
#717022 | #9406. Triangle | Purslane | WA | 6ms | 49272kb | C++14 | 3.9kb | 2024-11-06 16:40:14 | 2024-11-06 16:40:14 |
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]]!=son[u]) 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;
int del=0;
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],del+=str[u]*str[u]*str[i];
mp[lim+1].push_back({dfn[u],str[u]});
mp[dfn[u]].push_back({-lim-1,str[u]});
}
u=fa[u];
}
if(mp.size()) {
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 del+=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;
ans-=del/2;
}
}
cout<<ans<<'\n';
}
return 0;
}
详细
Test #1:
score: 100
Accepted
time: 6ms
memory: 48900kb
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: 0ms
memory: 48748kb
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: 3ms
memory: 48724kb
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: 49272kb
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 4934 11233 7950 5470 4525 5743 1590923
result:
wrong answer 11th lines differ - expected: '1586066', found: '1590923'