UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199792#546. 分组snow_trace10072ms11220kbC++782b2023-12-21 10:33:572023-12-21 12:03:12

answer

#include<bits/stdc++.h>
using namespace std;
int trie[300005][26],cnt[300005],tag[300005];int nw = 1;
string s[5005];int n;
void insert(string s){
	int now = 1;
	for(int  i =0;i<s.size();i++){
		if(!trie[now][s[i]-'A'])trie[now][s[i]-'A'] = ++nw;
		now = trie[now][s[i]-'A'];cnt[now]++;
	}return;
}int ans = 0;
void dfs(int now){
	for(int i =0;i<26;i++){
		if(trie[now][i])dfs(trie[now][i]),tag[now]+=tag[trie[now][i]];
	}if(now == 1)return;
	cnt[now]-=tag[now];
//	cout << now << " " << cnt[now] << endl;
	if(cnt[now]>=2)cnt[now]-=2,tag[now]+=2,ans+=2;
}
signed main(){
	cin >> n;
	for(int i = 1;i<=n;i++)cin >> s[i];
	for(int i = 1;i<=n;i++)reverse(s[i].begin(),s[i].end());
	for(int i = 1;i<=n;i++)insert(s[i]);
	dfs(1);cout << ans << endl;
	return 0;
}

Details

小提示:点击横条可展开更详细的信息

Subtask #1:

score: 20
Accepted

Test #1:

score: 20
Accepted
time: 0ms
memory: 1308kb

input:

2
CAAAECCCEDEECBEAE
EDECADAAADCACADE

output:

2

result:

ok "2"

Test #2:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

1
LKIEIDLCKFLCGCKJIJBACED

output:

0

result:

ok "0"

Test #3:

score: 0
Accepted
time: 0ms
memory: 1288kb

input:

1
N

output:

0

result:

ok "0"

Test #4:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

1
PPNOMCGAPHHJDJ

output:

0

result:

ok "0"

Test #5:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

1
BBK

output:

0

result:

ok "0"

Test #6:

score: 0
Accepted
time: 0ms
memory: 1300kb

input:

1
CBFBBFAABDEFC

output:

0

result:

ok "0"

Test #7:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

2
GIQHAOASGPJMQJKONKIHJRSHHTBTJANNGKMUPAKQAQILFN
FQJMJNBELCEQFDRTCGQGK

output:

0

result:

ok "0"

Test #8:

score: 0
Accepted
time: 0ms
memory: 1304kb

input:

1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

0

result:

ok "0"

Test #9:

score: 0
Accepted
time: 2ms
memory: 1304kb

input:

1
IFNNAAJOCCLECHIOCLHKFCGMHFH

output:

0

result:

ok "0"

Test #10:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

1
JJAAAGAHEGBFHCGAIFHGGACEDFCHCHJJCGDFJGEDEICDDAHAI

output:

0

result:

ok "0"

Subtask #2:

score: 20
Accepted

Test #11:

score: 20
Accepted
time: 0ms
memory: 1308kb

input:

4
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE

output:

2

result:

ok "2"

Test #12:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

3
JGAPJCOFFIAKD
JCOFBQDAMJLHNCMILCCGQLKBKBAIDKDHCNCBNLFP
ELJIKANDOKFMIDAPCNOIENEFLMOC

output:

0

result:

ok "0"

Test #13:

score: 0
Accepted
time: 1ms
memory: 1312kb

input:

2
BAACAD
ECECDBEDEBEDEBABACADAABADCEBECBABABBAEDBECBBBA

output:

0

result:

ok "0"

Test #14:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

2
TULORMUJFFQNPSJICFCHUNFRUCTNILJGTOHQB
CCNSDCCRBFLRSTDBHKUQOUHMPROGQJIABDCSESDAKAIHFBHPI

output:

0

result:

ok "0"

Test #15:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

6
CBICGFABIBDBEEHFFDIFFBCAFBAGEIDAGHFAEDE
GBAHICCGC
IHGIEBCCFDDEBEECCEEBHGDHCDDGECCBFF
DGBFGBEBHGEGI...

output:

2

result:

ok "2"

Test #16:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

5
HLLBAFBCGGJFJFIIDDDACCCDJHKI
FICLEIJHLHJBGBIJEEF
CHICKEHBBKLEKLEKBIJIJAICGIADHGKABCI
KHCIDIILHJFLG...

output:

2

result:

ok "2"

Test #17:

score: 0
Accepted
time: 0ms
memory: 1312kb

input:

4
WIUGWACETCIGKCNSFY
GOFVBP
XLXFBUXPQ
HLGAURGVZXNJMSRYQQYWERNV

output:

0

result:

ok "0"

Test #18:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

4
G
CAGBFBIEAGCGIAHHEIFCIAFBAADBCEIHGIACDAAGB
FFIECF
AFHCCCFEHBGF

output:

2

result:

ok "2"

Test #19:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

6
BFJAMCKLHEIMLDAGCFACALBDHIGKJGLMGMHACJCHBLJCAJ
KIHLGHFBHKLDKAACLKLCJBLEBAEBJMKDBFFKLKLD
CHABBIMHFF...

output:

2

result:

ok "2"

Test #20:

score: 0
Accepted
time: 2ms
memory: 1320kb

input:

5
MHBIEBHLABHCGBBGJMCLAJMKFEMJGGE
NNHONNAMMJEEMJIINNDGHHEJGNNGKJJDJNBJADBB
DFAMKCEDNNMLFNDNDGLLJHCCF...

output:

0

result:

ok "0"

Subtask #3:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 0ms
memory: 1312kb

input:

6
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCDD...

output:

2

result:

ok "2"

Test #22:

score: 0
Accepted
time: 2ms
memory: 1304kb

input:

1
APBPEFENOQJCAKNHQHM

output:

0

result:

ok "0"

Test #23:

score: 0
Accepted
time: 0ms
memory: 1304kb

input:

1
VHJFSVEKVBULFQURHMJVNTQRCWNXPLNIJEGWA

output:

0

result:

ok "0"

Test #24:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

1
EDDIIBFEGBRLOEORKLLQOPOFRHMENCR

output:

0

result:

ok "0"

Test #25:

score: 0
Accepted
time: 0ms
memory: 1308kb

input:

2
GIDGHKFHCJACDCHFBJIFEDEBCIDABJGIJ
AAAGAHEGBFHCGAIFHGGACEDFCHCH

output:

0

result:

ok "0"

Test #26:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

5
DFAEADDBAFECEBDFFEECBFFACD
FEABBEEFFAFCFBFACEDDECDDAECDBDBEDEDBCCFDCDFEACEBF
FDAEBEEFFEBEEDAECDAAE...

output:

2

result:

ok "2"

Test #27:

score: 0
Accepted
time: 0ms
memory: 1328kb

input:

8
LBAFBCGGJFJFII
DDACCCDJHKIIFICLEIJHLH
BGBIJEEFACHICKEHBBKLEKLEKBIJIJAICGIADHGKABCIFKHCID
ILHJFLGFJ...

output:

6

result:

ok "6"

Test #28:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

5
RPCKPGCJPKOKIEJPCGRAQQERFLIA
BAADKCNRQPRALDJA
BFFFIELFFAOQLLCFNQBGFFKHLGOIDQ
JDLKIEOLBCNBMNERLEQKH...

output:

2

result:

ok "2"

Test #29:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

3
DIDKCFLIAI
FLDJJGJHGBBABKJAADJGGKFGAECLACFKJDKFJELIDDHHFJA
CIJIJBIFJKJIDBJGLIAJHHIFHJHKLAFEEIAGKEC...

output:

0

result:

ok "0"

Test #30:

score: 0
Accepted
time: 0ms
memory: 1320kb

input:

6
CGB
GJMCLAJMKFEMJGGEENNHONNAMMJ
EMJIINNDGHHEJGNNGKJJDJNBJADBBIDFAMKCEDNNMLFND
DGLLJHCCFFMJNJHFALKC...

output:

0

result:

ok "0"

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 0ms
memory: 1436kb

input:

56
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCD...

output:

48

result:

ok "48"

Test #32:

score: 0
Accepted
time: 0ms
memory: 1328kb

input:

9
ARPCJLNGNIFQKEJKCEILOLRBCKNNMMOQMPDMA
QEOKINGQRMBGFQLECCAGPPJRPROLKJCCQEC
NBQFHLLIDLHHB
NGIBEQIMDP...

output:

2

result:

ok "2"

Test #33:

score: 0
Accepted
time: 0ms
memory: 1516kb

input:

84
AGCEDECJFKHBFGKKIDJJIEHCIFDDCCDGDDB
GG
DDAFCEHBECJEHCJHHBHJFHBABGIFJKIICBDFFDIC
ECFKIDBKECKJDCCHK...

output:

62

result:

ok "62"

Test #34:

score: 0
Accepted
time: 0ms
memory: 1384kb

input:

32
GEDFEBK
EIBHHKFDCEKGIBFGAJG
EEHDLAHKDDLFIH
IIFIGIGFIBFBIFHJCCEFCCBFIC
HGCLKCGEFCBJGCFJIJEBCICCJBI...

output:

22

result:

ok "22"

Test #35:

score: 0
Accepted
time: 0ms
memory: 1392kb

input:

41
BCABCBAACCBCAAAABBBACACBAAAACCCCCABA
BBCCABACCCCBACBCCACBBA
BCBCABCCACAABABB
AAABBCAABAA
ABBACBCA...

output:

40

result:

ok "40"

Test #36:

score: 0
Accepted
time: 0ms
memory: 1480kb

input:

77
DJDNFJAPAHPBNBMCOID
KAMMEMOQDOCNKPKALGLFFGBAOOKPPLB
ICLHOPDBMFHAQJ
BKLPNBELLFBJPCMAHKJLCMJHPJ
NDD...

output:

48

result:

ok "48"

Test #37:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

2
GAGICDBFHGFFEDAIHBHHHEFBBIFFCFID
GDFCIIIACFFICGFIIHIIFCCCEDHCDFGCBCBCHAGGGFDEECHCCH

output:

0

result:

ok "0"

Test #38:

score: 0
Accepted
time: 0ms
memory: 1460kb

input:

57
BGAGCBFCGAAGECDBDBGGBBDGFFBEFDCAADFEGEECDHHD
CHBBGEHABAE
ECEEGDGGAEHAHGFGGBFBBGGGDF
FAHGDEFAACHBC...

output:

50

result:

ok "50"

Test #39:

score: 0
Accepted
time: 0ms
memory: 1548kb

input:

91
DFLFVUFNVTOHTJGVNRMJUJSOUUPPRMOTAISQQLAHNOF
AMNRERBNBERENSAEJAEPEINHDP
NJTMFUMFJSKETBNTKFEAQATACV...

output:

54

result:

ok "54"

Test #40:

score: 0
Accepted
time: 0ms
memory: 1316kb

input:

5
ADDAADDBDBACCADDBDDBAADDACDDBAD
CADACACBCADCBCDADBBAC
ACAC
CDDCCACACADBCCBDADCADBADBADCCABCDBABACD...

output:

4

result:

ok "4"

Subtask #5:

score: 20
Accepted

Test #41:

score: 20
Accepted
time: 6ms
memory: 5996kb

input:

1956
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCC...

output:

1726

result:

ok "1726"

Test #42:

score: 0
Accepted
time: 7ms
memory: 10672kb

input:

3829
FBCBCCCEEDDBDFDEEFEFDBCBABFDEAA
ACDDCFDFFABEDEAFCFDBBAEEAAAADAACFCBCFABCAFCCFCDAEE
EAFDADDFACEA...

output:

3212

result:

ok "3212"

Test #43:

score: 0
Accepted
time: 5ms
memory: 3936kb

input:

996
LNNEEDH
EBHLBHBBIHHMLFOJEHCMDCFOAIEB
ELHBAKHKILGGCALAKN
LCMF
FHFANKHDG
JELGLABHMABFBHHALHOCJOBHE...

output:

656

result:

ok "656"

Test #44:

score: 0
Accepted
time: 12ms
memory: 11220kb

input:

4114
AADBADBECCDAACBB
CECDBDECDCEAEBDEDCADDDACCCDBE
CCADABECBEEEBEACCADCCEEDAAEEDAEEDCEDCDEEDDCBEDAD...

output:

3580

result:

ok "3580"

Test #45:

score: 0
Accepted
time: 8ms
memory: 7604kb

input:

2398
NECOONFCAGOELGFMLOJIDEEMKBJKBKKIAGBKECAE
OGNGNLOGAGOHJNHEJPMCBPQB
IHKNFIILIAIFGGJ
OIBACCOKEKKJM...

output:

1434

result:

ok "1434"

Test #46:

score: 0
Accepted
time: 4ms
memory: 5972kb

input:

1734
UAGA
VMSTUQLKKND
TUTGJNEBBFTOSOGUKOACMGJPIPJIDMKJRNEGMDHVPSWLFE
NPCCBOTVGIIBCTKKQIDWOTWHCVOGVOE...

output:

1072

result:

ok "1072"

Test #47:

score: 0
Accepted
time: 14ms
memory: 11144kb

input:

3958
BACBABECBDFEBAAACFFCDBEFFAFBEEFDFFCBFBFBFBCD
D
DDABEBCDBEFDAECDACFD
ACABCBAADEFCDDFAEECCD
EDDDA...

output:

3358

result:

ok "3358"

Test #48:

score: 0
Accepted
time: 0ms
memory: 1408kb

input:

1249
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAA...

output:

100

result:

ok "100"

Test #49:

score: 0
Accepted
time: 5ms
memory: 6864kb

input:

2081
JSSPPJFAAAGRBOMRVDFIILDQUSIHEHC
QBA
QLLRGNR
SBHJBUVFRCGR
JNMUDKPFCESRAJQNTDATDCNHTAFTAKIICPB
VF...

output:

1242

result:

ok "1242"

Test #50:

score: 0
Accepted
time: 4ms
memory: 5020kb

input:

1376
BDIHBNAFNKGCODANIONCOJCKAEHAMJDEIGLLHIMHHMADDGL
OMEI
MABFG
NC
MOHJMJGOJIKHLHELKGLFEOACOB
DDCAEB...

output:

852

result:

ok "852"

Extra Test:

score: 0
Extra Test Passed