QOJ.ac
QOJ
| ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
|---|---|---|---|---|---|---|---|---|---|
| #556906 | #6816. Invincible Hotwheels | Nt_Yester | RE | 12ms | 40516kb | C++20 | 7.4kb | 2024-09-10 22:06:59 | 2024-09-10 22:07:00 |
Judging History
answer
#include <algorithm>
#include <iostream>
#include <cstring>
#include <cstdio>
#include <string>
#include <vector>
#include <queue>
#include <set>
#include <map>
#define N 1000005
#define M 100005
using namespace std;
bool M1;
int n; string s[N];
vector<int> pos[N];
int cnt,head[N];
struct Node { int to,nxt; }e[N<<1];
void add(int u,int v) { e[++cnt]=Node{v,head[u]},head[u]=cnt; }
int tot,ch[N][26],fail[N],id[N],edp[N],_id[N],__id[N];
void ins(int id) {
int p=0;
for (int i=0;i<s[id].size();i++) {
int c=s[id][i]-'a';
if (!ch[p][c]) ch[p][c]=++tot;
p=ch[p][c]; pos[id].push_back(p);
}
if (!::id[p]) ::id[p]=id;
else if (!_id[p]) _id[p]=::id[p],::id[p]=id;
else __id[p]=_id[p],_id[p]=::id[p],::id[p]=id;
edp[id]=p;
}
void getfail() {
queue<int> q;
for (int i=0;i<26;i++)
if (ch[0][i]) q.push(ch[0][i]);
while (!q.empty()) {
int x=q.front(); q.pop();
for (int i=0;i<26;i++)
if (ch[x][i]) fail[ch[x][i]]=ch[fail[x]][i],q.push(ch[x][i]);
else ch[x][i]=ch[fail[x]][i];
}
}
int dfncnt,dfn[N],ed[N];
void dfs(int u) {
dfn[u]=++dfncnt;
if (id[fail[u]]) {
if (!id[u]) id[u]=id[fail[u]],_id[u]=_id[fail[u]],__id[u]=__id[fail[u]];
else if (!_id[u]) __id[u]=_id[fail[u]],_id[u]=id[fail[u]];
else if (!__id[u]) __id[u]=id[fail[u]];
}
for (int i=head[u];i;i=e[i].nxt) {
int v=e[i].to;
dfs(v);
}
ed[u]=dfncnt;
}
struct BIT1 {
int c[N];
int lowbit(int x) { return x&-x; }
void upd(int x,int k) { for (int i=x;i<=tot+1;i+=lowbit(i)) c[i]+=k; }
int ask(int x) { int res=0; for (int i=x;i;i-=lowbit(i)) res+=c[i]; return res; }
int ask(int l,int r) { return ask(r)-ask(l-1); }
}t1;
struct BIT2 {
int c1[N],c2[N],c3[N];
int lowbit(int x) { return x&-x; }
void upd(int x,int k) { x++; for (int i=x;i;i-=lowbit(i)) { c1[i]++; if (k>c2[i]) c3[i]=c2[i],c2[i]=k; else if (k>c3[i]) c3[i]=k; } }
void del(int x) { x++; for (int i=x;i;i-=lowbit(i)) c1[i]=c2[i]=c3[i]=0; }
int ask(int x) { x++; int res=0; for (int i=x;i<=tot+1;i+=lowbit(i)) res+=c1[i]; return res; }
pair<int,int> _ask(int x) {
x++; int res1=0,res2=0;
for (int i=x;i<=tot+1;i+=lowbit(i)) {
if (c2[i]>res1) {
res2=res1,res1=c2[i];
if (c3[i]>res2) res2=c3[i];
} else if (c2[i]>res2)
res2=c2[i];
}
return {res1,res2};
}
}t2;
int t[N],vis[N];
struct Tmp {
int l,r,id;
Tmp(int _l=0,int _r=0,int _id=0) { l=_l,r=_r,id=_id; }
};
int main() {
scanf("%d",&n);
for (int i=1;i<=n;i++) {
cin>>s[i];
ins(i);
}
getfail();
for (int i=1;i<=tot;i++)
add(fail[i],i);
dfs(0); int ans=0;
for (int i=1;i<=n;i++) {
vector<int> vid;
vector<Tmp> tmp1,tmp2;
for (int j=0;j<s[i].size();j++) {
if (j!=s[i].size()-1) {
if (id[pos[i][j]]) vid.push_back(id[pos[i][j]]);
if (_id[pos[i][j]]) vid.push_back(_id[pos[i][j]]);
} else {
if (_id[pos[i][j]]) vid.push_back(_id[pos[i][j]]);
if (__id[pos[i][j]]) vid.push_back(__id[pos[i][j]]);
}
}
sort(vid.begin(),vid.end());
vid.erase(unique(vid.begin(),vid.end()),vid.end());
for (int j:vid) t1.upd(dfn[edp[j]],1);
for (int j:vid)
if (t1.ask(dfn[edp[j]],ed[edp[j]])<=2) vis[j]=1;
for (int j:vid) t1.upd(dfn[edp[j]],-1);
for (int j=0;j<s[i].size();j++) {
if (j!=s[i].size()-1) {
if (vis[id[pos[i][j]]]==1 and id[pos[i][j]])
tmp1.emplace_back(j+1-s[id[pos[i][j]]].size(),j,id[pos[i][j]]),
vis[id[pos[i][j]]]=2;
if (vis[_id[pos[i][j]]]==1 and _id[pos[i][j]])
tmp1.emplace_back(j+1-s[_id[pos[i][j]]].size(),j,_id[pos[i][j]]),
vis[_id[pos[i][j]]]=2;
if (vis[id[pos[i][j]]] and id[pos[i][j]])
tmp2.emplace_back(j+1-s[id[pos[i][j]]].size(),j,id[pos[i][j]]);
if (vis[_id[pos[i][j]]] and _id[pos[i][j]])
tmp2.emplace_back(j+1-s[_id[pos[i][j]]].size(),j,_id[pos[i][j]]);
} else {
if (vis[_id[pos[i][j]]]==1 and _id[pos[i][j]])
tmp1.emplace_back(j+1-s[_id[pos[i][j]]].size(),j,_id[pos[i][j]]),
vis[_id[pos[i][j]]]=2;
if (vis[__id[pos[i][j]]]==1 and __id[pos[i][j]])
tmp1.emplace_back(j+1-s[__id[pos[i][j]]].size(),j,__id[pos[i][j]]),
vis[__id[pos[i][j]]]=2;
if (vis[_id[pos[i][j]]] and _id[pos[i][j]])
tmp2.emplace_back(j+1-s[_id[pos[i][j]]].size(),j,_id[pos[i][j]]);
if (vis[__id[pos[i][j]]] and __id[pos[i][j]])
tmp2.emplace_back(j+1-s[__id[pos[i][j]]].size(),j,__id[pos[i][j]]);
}
}
for (int j=0;j<s[i].size();j++)
vis[id[pos[i][j]]]=vis[_id[pos[i][j]]]=vis[__id[pos[i][j]]]=0;
sort(tmp1.begin(),tmp1.end(),[](Tmp tmp1,Tmp tmp2) {
return tmp1.l<tmp2.l;
});
sort(tmp2.begin(),tmp2.end(),[](Tmp tmp1,Tmp tmp2) {
return tmp1.l<tmp2.l;
});
int k=0,l=0;
for (int j=0;j<s[i].size();j++) {
while (k<tmp1.size() and tmp1[k].l==j) {
t2.upd(tmp1[k].r,tmp1[k].id);
k++;
}
while (l<tmp2.size() and tmp2[l].l==j) {
if (vis[tmp2[l].id]==-1) { ++l; continue; }
int num=t2.ask(tmp2[l].r);
auto [res1,res2]=t2._ask(tmp2[l].r);
if (num==1 and res1!=tmp2[l].id and res2!=tmp2[l].id) {
res1|=res2;
if (vis[tmp2[l].id] and vis[tmp2[l].id]!=res1) { vis[tmp2[l++].id]=-1; continue; }
vis[tmp2[l].id]=res1;
} else if (num==2 and (res1==tmp2[l].id or res2==tmp2[l].id)) {
if (res1==tmp2[l].id) res1=res2;
if (vis[tmp2[l].id] and vis[tmp2[l].id]!=res1) { vis[tmp2[l++].id]=-1; continue; }
vis[tmp2[l].id]=res1;
} else if (num>1) vis[tmp2[l].id]=-1;
++l;
}
}
int las=ans;
for (int j=0;j<s[i].size();j++) {
if (vis[id[pos[i][j]]]>0) ans++,vis[id[pos[i][j]]]=-1;
if (vis[_id[pos[i][j]]]>0) ans++,vis[_id[pos[i][j]]]=-1;
if (vis[__id[pos[i][j]]]>0) ans++,vis[__id[pos[i][j]]]=-1;
}
for (int j=0;j<s[i].size();j++)
vis[id[pos[i][j]]]=vis[_id[pos[i][j]]]=vis[__id[pos[i][j]]]=0;
for (auto j:tmp1)
t2.del(j.r);
// printf("%d: %d\n",i,ans-las);
}
printf("%d\n",ans);
return 0;
}
/*
19
babaada
aabaadabbb
ccb
aa
abaada
ccbaadba
ababaadac
baad
db
ababaadaccaaa
aadb
aabaabaadabbba
baebcababaadaccaaaababaa
abaadab
baebcababaadaccaaa
adba
aababaadacb
aadbba
baebcababaadaccaaaacbc
1: 1
2: 1
3: 0
4: 0
5: 1
6: 1
7: 1
8: 0
9: 0
10: 1
11: 0
12: 1
13: 1
14: 1
15: 1
16: 0
17: 1
18: 2
19: 1
1: 1
2: 1
3: 0
4: 0
5: 1
6: 0
7: 1
8: 0
9: 0
10: 1
11: 0
12: 1
13: 1
14: 1
15: 1
16: 0
17: 1
18: 2
19: 1
*/
Details
Tip: Click on the bar to expand more detailed information
Test #1:
score: 100
Accepted
time: 8ms
memory: 36996kb
input:
8 wwwsoupunetcom wwwsoupunet soupunet punetcom punet pun net n
output:
6
result:
ok 1 number(s): "6"
Test #2:
score: 0
Accepted
time: 4ms
memory: 40516kb
input:
4 a aa aaa aaaa
output:
2
result:
ok 1 number(s): "2"
Test #3:
score: 0
Accepted
time: 12ms
memory: 35852kb
input:
5 bc cbcb cbca cbc c
output:
3
result:
ok 1 number(s): "3"
Test #4:
score: 0
Accepted
time: 8ms
memory: 35808kb
input:
5 c ccaaaa caaa aa ccaaa
output:
3
result:
ok 1 number(s): "3"
Test #5:
score: 0
Accepted
time: 8ms
memory: 35992kb
input:
5 bbabc b bbba abb abbbbab
output:
0
result:
ok 1 number(s): "0"
Test #6:
score: 0
Accepted
time: 3ms
memory: 38080kb
input:
100 cccabcacaccbcacbbcaaabacacbbccaacacacacccbcaacaaaaaacbcbcbcaccccaccccbaaaabcaacbacabaccaaccbcccbabbcbbbaaabbcbbabccacbbabaac acacacccbcaacaaaaaacbcbcbcaccccaccccbaaaabca babaaccbbacbcacca acbbcaaabacacbbccaacacacacccbcaacaaaaaacbcbcbcaccccaccccbaaaabcaacbacabaccaaccbcccbabbcbbbaaabbcbbabccacbbab...
output:
202
result:
ok 1 number(s): "202"
Test #7:
score: 0
Accepted
time: 4ms
memory: 35532kb
input:
100 zdbbzzedhbzpphphpzbpbcddb cbhzdbbzzedhbzpphphpzbpbcddbhcbzcphee dbbzzedhbzp dbbzzedhbzpphphpzbpbcddbhcbzcpheeczzzhhabeephbhe bhzdbbzzedhbzpphphpzbpbcddbhcbzcpheeczzzhhabeephbhepczcdhd dhbzpphphpzbpbcddbhcbzcpheeczzzhhabeephbhepczcdhdaczadhad ac dhbzpphphpzbpbcddbh zzedhbzpphphpzbpbcddbhcbzcpheec...
output:
190
result:
ok 1 number(s): "190"
Test #8:
score: 0
Accepted
time: 8ms
memory: 39120kb
input:
100 abhpappzeddpdbezhzdhezpzcpchbhecdebpahacbpebdeppdbpepbeaehphheepeb ebcaacpdhcbcddhbhczahpchbzbzdhzzaddaaebabbphdbbeepdhpeazeaaapbdezhdeeedcpadbzbhheadpezpheddcdcbeedcdbdzbddpacaedazheddhheezzdaebeheeccachcaapazdpchpzdbpzeaahhczcppchazdephdzzeaahzbzzeabhppapezeaahzhdbzhchabazcczpdhhdhedbdbebhecph...
output:
204
result:
ok 1 number(s): "204"
Test #9:
score: 0
Accepted
time: 8ms
memory: 36420kb
input:
19 babaada aabaadabbb ccb aa abaada ccbaadba ababaadac baad db ababaadaccaaa aadb aabaabaadabbba baebcababaadaccaaaababaa abaadab baebcababaadaccaaa adba aababaadacb aadbba baebcababaadaccaaaacbc
output:
13
result:
ok 1 number(s): "13"
Test #10:
score: 0
Accepted
time: 3ms
memory: 39964kb
input:
23 aababa ababaaaadd b aad aaad aaababaaaa aaa aadaacbababaaaadbab acbababaaaadba aba ababa acbab ababaa aaababaaa babaaaad ddaaababaaaadd aadaacbababaaa bababaaa babaaaadaba aacbababaaaa abaaaa dacbababaaaa aaaa
output:
29
result:
ok 1 number(s): "29"
Test #11:
score: -100
Runtime Error
input:
28519 abbbaaaaaaaacabcacabbaadabcbaa cdaaacabbabc addaaaaabbaabcbbaabbccaaaacabaadbacbbbbaaabacacabbaadabcbbaaaabaecaaaaaadbaabdaabbacbaaacbbabbacecbbacbaabcaababbaaabdbaaacbbeaabadaabbcabdaabaacaaaaadabaac bbaadabcdebacbaaabbcaabbbaab bbcabbbaadaabbbaabc accaccbababbaacaaacabcacabcaabababaaaca aaaa...