UOJ Logo

NOI.AC

ID题目提交者结果用时内存语言文件大小提交时间测评时间
#199778#546. 分组wosile10026ms11620kbC++11795b2023-12-21 08:42:152023-12-21 12:01:30

answer

#include<bits/stdc++.h>
using namespace std;
int n;
string s[5005];
int tr[1000005][26],fa[1000005],cnt[1000005];
int tot=0;
vector<int>v[55];
int main(){
	ios::sync_with_stdio(false);
	cin.tie(0);
	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++){
		int cur=0;
		for(int j=0;j<(int)s[i].size();j++){
			int c=s[i][j]-'A';
			if(tr[cur][c]==0){
				tr[cur][c]=++tot;
				fa[tot]=cur;
				v[j+1].push_back(tot);
			}
			cur=tr[cur][c];
			cnt[cur]++;
		}
	}
	int ans=0;
	for(int i=50;i>=1;i--){
		for(int x:v[i])if(cnt[x]>=2){
			// cout<<x<<endl;
			int cur=x;
			while(cur){
				cnt[cur]-=2;
				cur=fa[cur];
			}
			ans+=2;
		}
	}
	cout<<ans;
	return 0;
}
//quod erat demonstrandum

详细

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

Subtask #1:

score: 20
Accepted

Test #1:

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

input:

2
CAAAECCCEDEECBEAE
EDECADAAADCACADE

output:

2

result:

ok "2"

Test #2:

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

input:

1
LKIEIDLCKFLCGCKJIJBACED

output:

0

result:

ok "0"

Test #3:

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

input:

1
N

output:

0

result:

ok "0"

Test #4:

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

input:

1
PPNOMCGAPHHJDJ

output:

0

result:

ok "0"

Test #5:

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

input:

1
BBK

output:

0

result:

ok "0"

Test #6:

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

input:

1
CBFBBFAABDEFC

output:

0

result:

ok "0"

Test #7:

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

input:

2
GIQHAOASGPJMQJKONKIHJRSHHTBTJANNGKMUPAKQAQILFN
FQJMJNBELCEQFDRTCGQGK

output:

0

result:

ok "0"

Test #8:

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

input:

1
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA

output:

0

result:

ok "0"

Test #9:

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

input:

1
IFNNAAJOCCLECHIOCLHKFCGMHFH

output:

0

result:

ok "0"

Test #10:

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

input:

1
JJAAAGAHEGBFHCGAIFHGGACEDFCHCHJJCGDFJGEDEICDDAHAI

output:

0

result:

ok "0"

Subtask #2:

score: 20
Accepted

Test #11:

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

input:

4
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE

output:

2

result:

ok "2"

Test #12:

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

input:

3
JGAPJCOFFIAKD
JCOFBQDAMJLHNCMILCCGQLKBKBAIDKDHCNCBNLFP
ELJIKANDOKFMIDAPCNOIENEFLMOC

output:

0

result:

ok "0"

Test #13:

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

input:

2
BAACAD
ECECDBEDEBEDEBABACADAABADCEBECBABABBAEDBECBBBA

output:

0

result:

ok "0"

Test #14:

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

input:

2
TULORMUJFFQNPSJICFCHUNFRUCTNILJGTOHQB
CCNSDCCRBFLRSTDBHKUQOUHMPROGQJIABDCSESDAKAIHFBHPI

output:

0

result:

ok "0"

Test #15:

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

input:

6
CBICGFABIBDBEEHFFDIFFBCAFBAGEIDAGHFAEDE
GBAHICCGC
IHGIEBCCFDDEBEECCEEBHGDHCDDGECCBFF
DGBFGBEBHGEGI...

output:

2

result:

ok "2"

Test #16:

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

input:

5
HLLBAFBCGGJFJFIIDDDACCCDJHKI
FICLEIJHLHJBGBIJEEF
CHICKEHBBKLEKLEKBIJIJAICGIADHGKABCI
KHCIDIILHJFLG...

output:

2

result:

ok "2"

Test #17:

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

input:

4
WIUGWACETCIGKCNSFY
GOFVBP
XLXFBUXPQ
HLGAURGVZXNJMSRYQQYWERNV

output:

0

result:

ok "0"

Test #18:

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

input:

4
G
CAGBFBIEAGCGIAHHEIFCIAFBAADBCEIHGIACDAAGB
FFIECF
AFHCCCFEHBGF

output:

2

result:

ok "2"

Test #19:

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

input:

6
BFJAMCKLHEIMLDAGCFACALBDHIGKJGLMGMHACJCHBLJCAJ
KIHLGHFBHKLDKAACLKLCJBLEBAEBJMKDBFFKLKLD
CHABBIMHFF...

output:

2

result:

ok "2"

Test #20:

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

input:

5
MHBIEBHLABHCGBBGJMCLAJMKFEMJGGE
NNHONNAMMJEEMJIINNDGHHEJGNNGKJJDJNBJADBB
DFAMKCEDNNMLFNDNDGLLJHCCF...

output:

0

result:

ok "0"

Subtask #3:

score: 20
Accepted

Test #21:

score: 20
Accepted
time: 1ms
memory: 1340kb

input:

6
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCDD...

output:

2

result:

ok "2"

Test #22:

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

input:

1
APBPEFENOQJCAKNHQHM

output:

0

result:

ok "0"

Test #23:

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

input:

1
VHJFSVEKVBULFQURHMJVNTQRCWNXPLNIJEGWA

output:

0

result:

ok "0"

Test #24:

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

input:

1
EDDIIBFEGBRLOEORKLLQOPOFRHMENCR

output:

0

result:

ok "0"

Test #25:

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

input:

2
GIDGHKFHCJACDCHFBJIFEDEBCIDABJGIJ
AAAGAHEGBFHCGAIFHGGACEDFCHCH

output:

0

result:

ok "0"

Test #26:

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

input:

5
DFAEADDBAFECEBDFFEECBFFACD
FEABBEEFFAFCFBFACEDDECDDAECDBDBEDEDBCCFDCDFEACEBF
FDAEBEEFFEBEEDAECDAAE...

output:

2

result:

ok "2"

Test #27:

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

input:

8
LBAFBCGGJFJFII
DDACCCDJHKIIFICLEIJHLH
BGBIJEEFACHICKEHBBKLEKLEKBIJIJAICGIADHGKABCIFKHCID
ILHJFLGFJ...

output:

6

result:

ok "6"

Test #28:

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

input:

5
RPCKPGCJPKOKIEJPCGRAQQERFLIA
BAADKCNRQPRALDJA
BFFFIELFFAOQLLCFNQBGFFKHLGOIDQ
JDLKIEOLBCNBMNERLEQKH...

output:

2

result:

ok "2"

Test #29:

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

input:

3
DIDKCFLIAI
FLDJJGJHGBBABKJAADJGGKFGAECLACFKJDKFJELIDDHHFJA
CIJIJBIFJKJIDBJGLIAJHHIFHJHKLAFEEIAGKEC...

output:

0

result:

ok "0"

Test #30:

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

input:

6
CGB
GJMCLAJMKFEMJGGEENNHONNAMMJ
EMJIINNDGHHEJGNNGKJJDJNBJADBBIDFAMKCEDNNMLFND
DGLLJHCCFFMJNJHFALKC...

output:

0

result:

ok "0"

Subtask #4:

score: 20
Accepted

Test #31:

score: 20
Accepted
time: 1ms
memory: 1468kb

input:

56
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCCCD...

output:

48

result:

ok "48"

Test #32:

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

input:

9
ARPCJLNGNIFQKEJKCEILOLRBCKNNMMOQMPDMA
QEOKINGQRMBGFQLECCAGPPJRPROLKJCCQEC
NBQFHLLIDLHHB
NGIBEQIMDP...

output:

2

result:

ok "2"

Test #33:

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

input:

84
AGCEDECJFKHBFGKKIDJJIEHCIFDDCCDGDDB
GG
DDAFCEHBECJEHCJHHBHJFHBABGIFJKIICBDFFDIC
ECFKIDBKECKJDCCHK...

output:

62

result:

ok "62"

Test #34:

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

input:

32
GEDFEBK
EIBHHKFDCEKGIBFGAJG
EEHDLAHKDDLFIH
IIFIGIGFIBFBIFHJCCEFCCBFIC
HGCLKCGEFCBJGCFJIJEBCICCJBI...

output:

22

result:

ok "22"

Test #35:

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

input:

41
BCABCBAACCBCAAAABBBACACBAAAACCCCCABA
BBCCABACCCCBACBCCACBBA
BCBCABCCACAABABB
AAABBCAABAA
ABBACBCA...

output:

40

result:

ok "40"

Test #36:

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

input:

77
DJDNFJAPAHPBNBMCOID
KAMMEMOQDOCNKPKALGLFFGBAOOKPPLB
ICLHOPDBMFHAQJ
BKLPNBELLFBJPCMAHKJLCMJHPJ
NDD...

output:

48

result:

ok "48"

Test #37:

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

input:

2
GAGICDBFHGFFEDAIHBHHHEFBBIFFCFID
GDFCIIIACFFICGFIIHIIFCCCEDHCDFGCBCBCHAGGGFDEECHCCH

output:

0

result:

ok "0"

Test #38:

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

input:

57
BGAGCBFCGAAGECDBDBGGBBDGFFBEFDCAADFEGEECDHHD
CHBBGEHABAE
ECEEGDGGAEHAHGFGGBFBBGGGDF
FAHGDEFAACHBC...

output:

50

result:

ok "50"

Test #39:

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

input:

91
DFLFVUFNVTOHTJGVNRMJUJSOUUPPRMOTAISQQLAHNOF
AMNRERBNBERENSAEJAEPEINHDP
NJTMFUMFJSKETBNTKFEAQATACV...

output:

54

result:

ok "54"

Test #40:

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

input:

5
ADDAADDBDBACCADDBDDBAADDACDDBAD
CADACACBCADCBCDADBBAC
ACAC
CDDCCACACADBCCBDADCADBADBADCCABCDBABACD...

output:

4

result:

ok "4"

Subtask #5:

score: 20
Accepted

Test #41:

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

input:

1956
CAAAECCCEDEECBEAE
EDECADAAADCACADE
ECABDEBBBEB
EACCADEEEDDECE
ACDCDDCEABC
CBBEECBBECEDDCDCDDCCC...

output:

1726

result:

ok "1726"

Test #42:

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

input:

3829
FBCBCCCEEDDBDFDEEFEFDBCBABFDEAA
ACDDCFDFFABEDEAFCFDBBAEEAAAADAACFCBCFABCAFCCFCDAEE
EAFDADDFACEA...

output:

3212

result:

ok "3212"

Test #43:

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

input:

996
LNNEEDH
EBHLBHBBIHHMLFOJEHCMDCFOAIEB
ELHBAKHKILGGCALAKN
LCMF
FHFANKHDG
JELGLABHMABFBHHALHOCJOBHE...

output:

656

result:

ok "656"

Test #44:

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

input:

4114
AADBADBECCDAACBB
CECDBDECDCEAEBDEDCADDDACCCDBE
CCADABECBEEEBEACCADCCEEDAAEEDAEEDCEDCDEEDDCBEDAD...

output:

3580

result:

ok "3580"

Test #45:

score: 0
Accepted
time: 6ms
memory: 7816kb

input:

2398
NECOONFCAGOELGFMLOJIDEEMKBJKBKKIAGBKECAE
OGNGNLOGAGOHJNHEJPMCBPQB
IHKNFIILIAIFGGJ
OIBACCOKEKKJM...

output:

1434

result:

ok "1434"

Test #46:

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

input:

1734
UAGA
VMSTUQLKKND
TUTGJNEBBFTOSOGUKOACMGJPIPJIDMKJRNEGMDHVPSWLFE
NPCCBOTVGIIBCTKKQIDWOTWHCVOGVOE...

output:

1072

result:

ok "1072"

Test #47:

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

input:

3958
BACBABECBDFEBAAACFFCDBEFFAFBEEFDFFCBFBFBFBCD
D
DDABEBCDBEFDAECDACFD
ACABCBAADEFCDDFAEECCD
EDDDA...

output:

3358

result:

ok "3358"

Test #48:

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

input:

1249
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAAA
AAAAAAAAAAAAA
AAAAAAAAA...

output:

100

result:

ok "100"

Test #49:

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

input:

2081
JSSPPJFAAAGRBOMRVDFIILDQUSIHEHC
QBA
QLLRGNR
SBHJBUVFRCGR
JNMUDKPFCESRAJQNTDATDCNHTAFTAKIICPB
VF...

output:

1242

result:

ok "1242"

Test #50:

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

input:

1376
BDIHBNAFNKGCODANIONCOJCKAEHAMJDEIGLLHIMHHMADDGL
OMEI
MABFG
NC
MOHJMJGOJIKHLHELKGLFEOACOB
DDCAEB...

output:

852

result:

ok "852"

Extra Test:

score: 0
Extra Test Passed