QOJ.ac

QOJ

ID	Problem	Submitter	Result	Time	Memory	Language	File size	Submit time	Judge time
#224728	#3844. LCS Spanning Tree	C1942huangjiaxu	WA	1131ms	535640kb	C++14	1.4kb	2023-10-23 12:08:15	2023-10-23 12:08:15

Judging History

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

[2023-10-23 12:08:15]
评测

测评结果：WA
用时：1131ms
内存：535640kb

查看

[2023-10-23 12:08:15]
提交

answer

#include<bits/stdc++.h>
using namespace std;
const int N=4e6+5;
struct node{
	int fa,ch[26],ln;
}tr[N];
int cnt=1,ls,n,id[N],pa[N];
long long ans;
char s[N];
vector<int>e[N];
bool cmp(int x,int y){
	return tr[x].ln>tr[y].ln;
}
int ins(int c){
	int p=ls;
	if(tr[p].ch[c]){
		int q=tr[p].ch[c];
		if(tr[q].ln==tr[p].ln+1)return q;
		int nq=++cnt;tr[nq]=tr[q];
		tr[nq].ln=tr[p].ln+1,tr[q].fa=nq;
		for(;p&&tr[p].ch[c]==q;p=tr[p].fa)tr[p].ch[c]=nq;
		return nq;
	}
	int np=++cnt;
	tr[np].ln=tr[p].ln+1;
	for(;p&&!tr[p].ch[c];p=tr[p].fa)tr[p].ch[c]=np;
	if(!p)tr[np].fa=1;
	else{
		int q=tr[p].ch[c];
		if(tr[q].ln==tr[p].ln+1)tr[np].fa=q;
		else{
			int nq=++cnt;tr[nq]=tr[q];
			tr[nq].ln=tr[p].ln+1,tr[np].fa=tr[q].fa=nq;
			for(;p&&tr[p].ch[c]==q;p=tr[p].fa)tr[p].ch[c]=nq;
		}
	}
	return np;
}
int gp(int x){
	return pa[x]==x?pa[x]:pa[x]=gp(pa[x]);
}
void add(int x){
	scanf("%s",s+1),ls=1;
	int l=strlen(s+1);
	for(int i=1;i<=l;++i)ls=ins(s[i]-'a'),e[ls].push_back(x);
}
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)add(i);
	for(int i=1;i<=cnt;++i)id[i]=pa[i]=i;
	sort(id+1,id+cnt+1,cmp);
	for(int i=1,x;i<=cnt;++i){
		x=id[i];
		if(e[x].empty())continue;
		int u=gp(e[x][0]);
		for(auto v:e[x])if(gp(v)!=u){
			ans+=tr[x].ln;
			pa[gp(v)]=u;
		}
		e[tr[x].fa].push_back(u);
	}
	printf("%lld\n",ans);
	return 0;
}

Source code, Language: C++14

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 100

Accepted

time: 10ms

memory: 105768kb

input:

4
icpc
macau
regional
contest

output:

result:

ok single line: '4'

Test #2:

score: 0

Accepted

time: 8ms

memory: 105112kb

input:

3
ababa
babab
aba

output:

result:

ok single line: '7'

Test #3:

score: 0

Accepted

time: 611ms

memory: 403000kb

input:

26
aaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaaa...

output:

result:

ok single line: '0'

Test #4:

score: 0

Accepted

time: 12ms

memory: 104388kb

input:

7
jia
ran
jin
tian
chi
shen
me

output:

result:

ok single line: '9'

Test #5:

score: 0

Accepted

time: 15ms

memory: 104852kb

input:

10
theysaynothinglastsforever
weareonlyheretoday
loveisnowornever
bringmefaraway
takemetoyourheart
takemetoyoursoul
givemeyourhandandholdme
showmewhatloveis
bemyguidingstar
itiseasytakemetoyourheart

output:

result:

ok single line: '55'

Test #6:

score: 0

Accepted

time: 17ms

memory: 107828kb

input:

100
dblkekaekijliimalcaidjjfaghdmhifkiebieffbddjmflkhagajcfmkccjjadgiijdbdldgbbhgcfdcadbeiabkemiefdccmhdcfilhkfabmfdmigfgigdcibgaeicedfiidgecbhdamiaiefbmbgbjhklbhafmhckklbmmiemkcbfgjihmdjkai
bciiecmbc
cdjailkkbefkbmlekiefdhklcbdccfbgkagflfemjjmkjmcgiibldlmhbcldjajgafmakfbhecgcckkkglklljhmliehidbkicm...

output:

result:

ok single line: '476'

Test #7:

score: 0

Accepted

time: 1131ms

memory: 535640kb

input:

2000
ecbhcebgbcjgjiihdefajfbbaajfjdedggciaegdiijhijgedbgejhgjjfhabdfhbihdeegcehbcjhgebcjachbdeiefejefhcjdihfcfgeegdahhjhjiiffjjadifiijjbhhjjeffabiaagcjhaachjbiecfeceefddecjchjfibgedfdghgdijdcdahfeddjihbhbbghjjffdcibaggiiadbaajhfcgdbaafbicahjhabfdbeacccfdehebciafaaffdfjdciafbhidbahdccjhjdadcciecfbhac...

output:

result:

ok single line: '17765'

Test #8:

score: 0

Accepted

time: 1035ms

memory: 511828kb

input:

1413
gjjmlceglbmbibjmmfcfmickcllfekgmicmifdbfgdgbeecgjgalbfkdfljjkclfgkaacdgigblaiaiehkeiccbjamikdgcjfemhhfebicddelklibjafmjhleebkimeblljfembgcgacdlkhjmbijjgacjaajebjfkcllffalheefeaedbmmkicaeecckdmedddbikeieimjmmcfdcgamicfbeimkjfamidjfhejdgiehkjkbdaaaeieldfibkkcgallieiamfehcdggiigkabblgigjgdlmflmafj...

output:

result:

ok single line: '11429'

Test #9:

score: -100

Wrong Answer

time: 88ms

memory: 119308kb

input:

2000000
j
o
v
p
h
b
t
s
x
y
u
c
t
n
p
l
b
e
c
v
d
c
p
s
u
m
d
d
i
m
h
t
a
e
j
i
i
c
c
h
d
x
j
w
m
a
j
p
f
l
n
i
q
c
c
k
q
g
q
b
u
z
u
v
d
d
f
n
i
j
v
n
i
e
l
w
h
v
m
m
i
z
w
y
d
z
l
w
h
b
x
b
a
r
y
d
x
f
r
h
p
o
u
x
u
f
u
b
c
i
p
l
j
o
j
o
n
u
k
w
x
h
z
x
z
y
d
y
d
w
h
u
k
b
u
e
i
o
g
n
y
x
y
h
l
j
...

output:

result:

wrong answer 1st lines differ - expected: '1999974', found: '27'