UOJ Logo

NOI.AC

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#199784#546. 分组tkswls100162ms11548kbC++11693b2023-12-21 09:40:412023-12-21 12:01:59

answer

#include <bits/stdc++.h>
using namespace std;
int n, ans, son[250005][29], ccnt, a[250005];
string s, st;
inline void add(int p, string s, int q) {
	if (!son[p][s[q] - 'A']) {
		son[p][s[q] - 'A'] = ++ccnt;
	}
	if (q != 0) {
		add(son[p][s[q] - 'A'], s, q - 1);
	} else {
		a[son[p][s[q] - 'A']]++;
	}
}
inline int dfs(int p) {
	int cnt = a[p];
	for (int i = 0; i < 26; i++) {
		if (son[p][i]) cnt += dfs(son[p][i]);
	}
	if (p && cnt >= 2) {
		cnt -= 2, ans+=2;
	}
	return cnt;
}
signed main() {
	ios::sync_with_stdio(0);
	cin.tie(0);
	cout.tie(0);
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> s;
		add(0, s, s.size() - 1);
	}
	dfs(0);
	cout << ans;
}

Details

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

Subtask #1:

score: 20
Accepted

Test #1:

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

input:

2
CAAAECCCEDEECBEAE
EDECADAAADCACADE

output:

2

result:

ok "2"

Test #2:

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

input:

1
LKIEIDLCKFLCGCKJIJBACED

output:

0

result:

ok "0"

Test #3:

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

input:

1
N

output:

0

result:

ok "0"

Test #4:

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

input:

1
PPNOMCGAPHHJDJ

output:

0

result:

ok "0"

Test #5:

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

input:

1
BBK

output:

0

result:

ok "0"

Test #6:

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

input:

1
CBFBBFAABDEFC

output:

0

result:

ok "0"

Test #7:

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

input:

2
GIQHAOASGPJMQJKONKIHJRSHHTBTJANNGKMUPAKQAQILFN
FQJMJNBELCEQFDRTCGQGK

output:

0

result:

ok "0"

Test #8:

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

input:

1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

0

result:

ok "0"

Test #9:

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

input:

1
IFNNAAJOCCLECHIOCLHKFCGMHFH

output:

0

result:

ok "0"

Test #10:

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

input:

1
JJAAAGAHEGBFHCGAIFHGGACEDFCHCHJJCGDFJGEDEICDDAHAI

output:

0

result:

ok "0"

Subtask #2:

score: 20
Accepted

Test #11:

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

input:

4
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE

output:

2

result:

ok "2"

Test #12:

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

input:

3
JGAPJCOFFIAKD
JCOFBQDAMJLHNCMILCCGQLKBKBAIDKDHCNCBNLFP
ELJIKANDOKFMIDAPCNOIENEFLMOC

output:

0

result:

ok "0"

Test #13:

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

input:

2
BAACAD
ECECDBEDEBEDEBABACADAABADCEBECBABABBAEDBECBBBA

output:

0

result:

ok "0"

Test #14:

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

input:

2
TULORMUJFFQNPSJICFCHUNFRUCTNILJGTOHQB
CCNSDCCRBFLRSTDBHKUQOUHMPROGQJIABDCSESDAKAIHFBHPI

output:

0

result:

ok "0"

Test #15:

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

input:

6
CBICGFABIBDBEEHFFDIFFBCAFBAGEIDAGHFAEDE
GBAHICCGC
IHGIEBCCFDDEBEECCEEBHGDHCDDGECCBFF
DGBFGBEBHGEGI...

output:

2

result:

ok "2"

Test #16:

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

input:

5
HLLBAFBCGGJFJFIIDDDACCCDJHKI
FICLEIJHLHJBGBIJEEF
CHICKEHBBKLEKLEKBIJIJAICGIADHGKABCI
KHCIDIILHJFLG...

output:

2

result:

ok "2"

Test #17:

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

input:

4
WIUGWACETCIGKCNSFY
GOFVBP
XLXFBUXPQ
HLGAURGVZXNJMSRYQQYWERNV

output:

0

result:

ok "0"

Test #18:

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

input:

4
G
CAGBFBIEAGCGIAHHEIFCIAFBAADBCEIHGIACDAAGB
FFIECF
AFHCCCFEHBGF

output:

2

result:

ok "2"

Test #19:

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

input:

6
BFJAMCKLHEIMLDAGCFACALBDHIGKJGLMGMHACJCHBLJCAJ
KIHLGHFBHKLDKAACLKLCJBLEBAEBJMKDBFFKLKLD
CHABBIMHFF...

output:

2

result:

ok "2"

Test #20:

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

input:

5
MHBIEBHLABHCGBBGJMCLAJMKFEMJGGE
NNHONNAMMJEEMJIINNDGHHEJGNNGKJJDJNBJADBB
DFAMKCEDNNMLFNDNDGLLJHCCF...

output:

0

result:

ok "0"

Subtask #3:

score: 20
Accepted

Test #21:

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

input:

6
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCDD...

output:

2

result:

ok "2"

Test #22:

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

input:

1
APBPEFENOQJCAKNHQHM

output:

0

result:

ok "0"

Test #23:

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

input:

1
VHJFSVEKVBULFQURHMJVNTQRCWNXPLNIJEGWA

output:

0

result:

ok "0"

Test #24:

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

input:

1
EDDIIBFEGBRLOEORKLLQOPOFRHMENCR

output:

0

result:

ok "0"

Test #25:

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

input:

2
GIDGHKFHCJACDCHFBJIFEDEBCIDABJGIJ
AAAGAHEGBFHCGAIFHGGACEDFCHCH

output:

0

result:

ok "0"

Test #26:

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

input:

5
DFAEADDBAFECEBDFFEECBFFACD
FEABBEEFFAFCFBFACEDDECDDAECDBDBEDEDBCCFDCDFEACEBF
FDAEBEEFFEBEEDAECDAAE...

output:

2

result:

ok "2"

Test #27:

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

input:

8
LBAFBCGGJFJFII
DDACCCDJHKIIFICLEIJHLH
BGBIJEEFACHICKEHBBKLEKLEKBIJIJAICGIADHGKABCIFKHCID
ILHJFLGFJ...

output:

6

result:

ok "6"

Test #28:

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

input:

5
RPCKPGCJPKOKIEJPCGRAQQERFLIA
BAADKCNRQPRALDJA
BFFFIELFFAOQLLCFNQBGFFKHLGOIDQ
JDLKIEOLBCNBMNERLEQKH...

output:

2

result:

ok "2"

Test #29:

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

input:

3
DIDKCFLIAI
FLDJJGJHGBBABKJAADJGGKFGAECLACFKJDKFJELIDDHHFJA
CIJIJBIFJKJIDBJGLIAJHHIFHJHKLAFEEIAGKEC...

output:

0

result:

ok "0"

Test #30:

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

input:

6
CGB
GJMCLAJMKFEMJGGEENNHONNAMMJ
EMJIINNDGHHEJGNNGKJJDJNBJADBBIDFAMKCEDNNMLFND
DGLLJHCCFFMJNJHFALKC...

output:

0

result:

ok "0"

Subtask #4:

score: 20
Accepted

Test #31:

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

input:

56
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCD...

output:

48

result:

ok "48"

Test #32:

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

input:

9
ARPCJLNGNIFQKEJKCEILOLRBCKNNMMOQMPDMA
QEOKINGQRMBGFQLECCAGPPJRPROLKJCCQEC
NBQFHLLIDLHHB
NGIBEQIMDP...

output:

2

result:

ok "2"

Test #33:

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

input:

84
AGCEDECJFKHBFGKKIDJJIEHCIFDDCCDGDDB
GG
DDAFCEHBECJEHCJHHBHJFHBABGIFJKIICBDFFDIC
ECFKIDBKECKJDCCHK...

output:

62

result:

ok "62"

Test #34:

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

input:

32
GEDFEBK
EIBHHKFDCEKGIBFGAJG
EEHDLAHKDDLFIH
IIFIGIGFIBFBIFHJCCEFCCBFIC
HGCLKCGEFCBJGCFJIJEBCICCJBI...

output:

22

result:

ok "22"

Test #35:

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

input:

41
BCABCBAACCBCAAAABBBACACBAAAACCCCCABA
BBCCABACCCCBACBCCACBBA
BCBCABCCACAABABB
AAABBCAABAA
ABBACBCA...

output:

40

result:

ok "40"

Test #36:

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

input:

77
DJDNFJAPAHPBNBMCOID
KAMMEMOQDOCNKPKALGLFFGBAOOKPPLB
ICLHOPDBMFHAQJ
BKLPNBELLFBJPCMAHKJLCMJHPJ
NDD...

output:

48

result:

ok "48"

Test #37:

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

input:

2
GAGICDBFHGFFEDAIHBHHHEFBBIFFCFID
GDFCIIIACFFICGFIIHIIFCCCEDHCDFGCBCBCHAGGGFDEECHCCH

output:

0

result:

ok "0"

Test #38:

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

input:

57
BGAGCBFCGAAGECDBDBGGBBDGFFBEFDCAADFEGEECDHHD
CHBBGEHABAE
ECEEGDGGAEHAHGFGGBFBBGGGDF
FAHGDEFAACHBC...

output:

50

result:

ok "50"

Test #39:

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

input:

91
DFLFVUFNVTOHTJGVNRMJUJSOUUPPRMOTAISQQLAHNOF
AMNRERBNBERENSAEJAEPEINHDP
NJTMFUMFJSKETBNTKFEAQATACV...

output:

54

result:

ok "54"

Test #40:

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

input:

5
ADDAADDBDBACCADDBDDBAADDACDDBAD
CADACACBCADCBCDADBBAC
ACAC
CDDCCACACADBCCBDADCADBADBADCCABCDBABACD...

output:

4

result:

ok "4"

Subtask #5:

score: 20
Accepted

Test #41:

score: 20
Accepted
time: 7ms
memory: 6144kb

input:

1956
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCC...

output:

1726

result:

ok "1726"

Test #42:

score: 0
Accepted
time: 33ms
memory: 10996kb

input:

3829
FBCBCCCEEDDBDFDEEFEFDBCBABFDEAA
ACDDCFDFFABEDEAFCFDBBAEEAAAADAACFCBCFABCAFCCFCDAEE
EAFDADDFACEA...

output:

3212

result:

ok "3212"

Test #43:

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

input:

996
LNNEEDH
EBHLBHBBIHHMLFOJEHCMDCFOAIEB
ELHBAKHKILGGCALAKN
LCMF
FHFANKHDG
JELGLABHMABFBHHALHOCJOBHE...

output:

656

result:

ok "656"

Test #44:

score: 0
Accepted
time: 22ms
memory: 11548kb

input:

4114
AADBADBECCDAACBB
CECDBDECDCEAEBDEDCADDDACCCDBE
CCADABECBEEEBEACCADCCEEDAAEEDAEEDCEDCDEEDDCBEDAD...

output:

3580

result:

ok "3580"

Test #45:

score: 0
Accepted
time: 17ms
memory: 7824kb

input:

2398
NECOONFCAGOELGFMLOJIDEEMKBJKBKKIAGBKECAE
OGNGNLOGAGOHJNHEJPMCBPQB
IHKNFIILIAIFGGJ
OIBACCOKEKKJM...

output:

1434

result:

ok "1434"

Test #46:

score: 0
Accepted
time: 16ms
memory: 6136kb

input:

1734
UAGA
VMSTUQLKKND
TUTGJNEBBFTOSOGUKOACMGJPIPJIDMKJRNEGMDHVPSWLFE
NPCCBOTVGIIBCTKKQIDWOTWHCVOGVOE...

output:

1072

result:

ok "1072"

Test #47:

score: 0
Accepted
time: 26ms
memory: 11480kb

input:

3958
BACBABECBDFEBAAACFFCDBEFFAFBEEFDFFCBFBFBFBCD
D
DDABEBCDBEFDAECDACFD
ACABCBAADEFCDDFAEECCD
EDDDA...

output:

3358

result:

ok "3358"

Test #48:

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

input:

1249
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAA...

output:

100

result:

ok "100"

Test #49:

score: 0
Accepted
time: 9ms
memory: 7056kb

input:

2081
JSSPPJFAAAGRBOMRVDFIILDQUSIHEHC
QBA
QLLRGNR
SBHJBUVFRCGR
JNMUDKPFCESRAJQNTDATDCNHTAFTAKIICPB
VF...

output:

1242

result:

ok "1242"

Test #50:

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

input:

1376
BDIHBNAFNKGCODANIONCOJCKAEHAMJDEIGLLHIMHHMADDGL
OMEI
MABFG
NC
MOHJMJGOJIKHLHELKGLFEOACOB
DDCAEB...

output:

852

result:

ok "852"

Extra Test:

score: 0
Extra Test Passed