QOJ.ac

QOJ

IDProblemSubmitterResultTimeMemoryLanguageFile sizeSubmit timeJudge time
#397218#2791. 背单词james1BadCreeper100 ✓35ms48664kbC++141.3kb2024-04-23 19:45:562024-04-23 19:45:58

Judging History

This is the latest submission verdict.

  • [2024-04-23 19:45:58]
  • Judged
  • Verdict: 100
  • Time: 35ms
  • Memory: 48664kb
  • [2024-04-23 19:45:56]
  • Submitted

answer

#include <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <vector>

using namespace std;
typedef long long i64;

i64 ans = 0;
int n, ch[510005][26], tot = 0, cnt = 0;
int siz[500005], dfn[500005], lst[500005];
char s[500005];
bool e[510005];
vector<int> G[500005];

bool cmp(int x, int y) {
    return siz[x] < siz[y];
}

void dfs(int x, int fa) {
    if (e[x]) G[lst[x]].emplace_back(x), lst[x] = x;
    for (int i = 0; i < 26; ++i)
        if (ch[x][i]) lst[ch[x][i]] = lst[x], dfs(ch[x][i], lst[x]);
}

void dfs2(int x, int fa) {
    siz[x] = 1;
    for (int y : G[x]) {
        dfs2(y, x);
        siz[x] += siz[y];
    }
    sort(G[x].begin(), G[x].end(), cmp);
}

void dfs3(int x, int fa) {
    dfn[x] = ++cnt; ans += dfn[x] - dfn[fa];
    for (int y : G[x]) dfs3(y, x);
}

int main(void) {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) {
        scanf("%s", s);
        reverse(s, s + strlen(s));
        int x = 0;
        for (int i = 0; s[i]; ++i) {
            int c = s[i] - 'a';
            if (!ch[x][c]) ch[x][c] = ++tot;
            x = ch[x][c];
        }
        e[x] = true;
    }
    dfs(0, 0);
    dfs2(0, 0);
    dfs3(0, 0);
    printf("%lld\n", ans);
    return 0;
}

Details

Tip: Click on the bar to expand more detailed information

Test #1:

score: 10
Accepted
time: 2ms
memory: 21972kb

input:

8
bapynrrkcnnvsovfbqcdtolwmtiwcqbtgolxshonajnbqmpaagkfheunqbtujaaqaibynjuprrrdfmpnededwdyfvjiyximuthqlxxgxtxxptlgdpniejjrpfscdpqbckggqsgacitxacvpmipxgmchvvxswbprbgdwvnlmaggwmppfibpmhufmijdggascveireauwxygtdsdlnwnlwdmvcguyfbgakypgobauyjdaswykivweqqrmcyyadgyqatccjjphouvdxbcdpkyfofhcplhsijyiuhjfsgwgngh...

output:

21

result:

ok single line: '21'

Test #2:

score: 10
Accepted
time: 0ms
memory: 20368kb

input:

8
bmnqlmkiwtb
cbmnblmkiwtb
dbmnqlmkiwta
edbmnqlmkiwtbbbbb
fmnqlmkiwtg
gedbmaqlmkiwtc
hmnqlmkiwtbccc
icbmnqlmkiwtx

output:

36

result:

ok single line: '36'

Test #3:

score: 10
Accepted
time: 5ms
memory: 20200kb

input:

8
btksxyplffh
cbtksxyplffh
dcbtksxyplffh
wecbtksxyplffh
fcbtksxyplffh
dgcbtksxyplffh
chcbtksxyplffh
aiecbtksxyplffh

output:

23

result:

ok single line: '23'

Test #4:

score: 10
Accepted
time: 8ms
memory: 31968kb

input:

20
aaarpobpxbhkahntdgjyjflsnaowvpvegluhtdussinyoiflmvcgirpdqpcpwmmemqwqvbvbbiytxqefvggcyekbhyblckydkkdpjmhibapprrneljutfohvtoivnudhjjgvkgqonwreyukvsgfagkoufkidoynymesteeirxmalivyqdcgjhniwbfuxrjfrirvnhnmxwheyldyqsedycfmhcgpltuxtqllvnuimtslrsvwogelccjpvlbypmhbpogbstgqnvmtfgbyxjesepyaiaumpkhgrkwnwtlfvt...

output:

78

result:

ok single line: '78'

Test #5:

score: 10
Accepted
time: 3ms
memory: 28884kb

input:

20
iuysiukbiqtgkecuhxolnknbvpwlajsyxwkvlmekkaxdrilidrijeyqbjskjjbsgblnpceturdhorjkrkartficsqmgucegidcihhaxkqmgepollbeytlqrjnskemgghqfuheffrqfgcpyttonlbikawvmgqvavksglucowoftywxtkkfnadkylvbybyyapatwuhcekwvtlmpirxrrewfdnkpbpkvcxhmwrisxpykofumrmfeociiumpedmjduotfqfqjqhpibgsntfbrgokpcrruydnshohdiqqmgftx...

output:

63

result:

ok single line: '63'

Test #6:

score: 10
Accepted
time: 21ms
memory: 32516kb

input:

100000
aaaaa
baaaa
caaaa
daaaa
eaaaa
faaaa
gaaaa
haaaa
iaaaa
jaaaa
kaaaa
laaaa
maaaa
naaaa
oaaaa
paaaa
qaaaa
raaaa
saaaa
taaaa
uaaaa
vaaaa
waaaa
xaaaa
yaaaa
zaaaa
abaaa
bbaaa
cbaaa
dbaaa
ebaaa
fbaaa
gbaaa
hbaaa
ibaaa
jbaaa
kbaaa
lbaaa
mbaaa
nbaaa
obaaa
pbaaa
qbaaa
rbaaa
sbaaa
tbaaa
ubaaa
vbaaa
wbaaa...

output:

5000050000

result:

ok single line: '5000050000'

Test #7:

score: 10
Accepted
time: 35ms
memory: 44464kb

input:

71948
aa
aaadoatm
aaadxq
aaaxg
aab
aabd
aablfs
aablqbwdhbld
aabwkwbx
aac
aaciwiqtw
aackxk
aacrmt
aacwaaotd
aacx
aadgjd
aadr
aadrnrwsybm
aadx
aaehrq
aaejrrmtklc
aaeswlrw
aaew
aaf
aafajycoh
aafofpat
aafrekv
aafuodufxmkxdfqtww
aafvbrce
aag
aagpjcwq
aagqog
aaguj
aahdp
aahm
aaht
aahwgdwra
aai
aaifqm
aaig...

output:

20852375

result:

ok single line: '20852375'

Test #8:

score: 10
Accepted
time: 32ms
memory: 48664kb

input:

68598
aa
aaavuisgjjcob
aab
aabcjovucv
aabnvyk
aabs
aabxm
aacbdj
aacblqfkdmsmvv
aacew
aacfyhktyxxss
aackcy
aacpsmsgleserxpakqr
aad
aadjlnkmfc
aadlop
aadn
aadppwutvcbeucgycvr
aae
aaegei
aaey
aaf
aafjbsyijtpppu
aafswbqtcbehaid
aaft
aafygykobqubn
aagb
aagbwtoxaqkqp
aagdhvqx
aah
aahjfnu
aahkn
aahq
aahuvk...

output:

19408621

result:

ok single line: '19408621'

Test #9:

score: 10
Accepted
time: 21ms
memory: 38536kb

input:

88564
aa
aaa
aaadsv
aaaemhwgcx
aaaey
aaak
aaaock
aaauamc
aaawsaayv
aab
aabmaa
aabmyc
aabp
aabtvs
aabx
aabxn
aac
aacf
aacgvfuu
aacjxou
aackdedfs
aaclbo
aad
aaddspj
aaded
aadsv
aae
aaea
aaeck
aaegs
aaeiqt
aaeka
aaelg
aaeow
aaf
aafa
aafd
aaffwry
aafh
aafhqr
aafrd
aafty
aafuu
aafyf
aafyuq
aag
aagigac
aa...

output:

24603126

result:

ok single line: '24603126'

Test #10:

score: 10
Accepted
time: 23ms
memory: 34328kb

input:

100000
wjag
kpvco
lf
it
bpw
hhk
bimi
hm
cj
elgi
pdbmu
nd
prwvk
qd
awyd
immcj
fyeem
igoiu
td
py
gxexd
gjqnx
oopr
tcqph
iq
mdh
xnang
ouei
mw
bbb
qwty
gnsy
wbny
wam
kml
jvh
tayyx
wxyt
aogj
jw
wciee
xg
hlfou
nia
bjy
dyhr
usmwn
cmx
oicr
jyd
yw
fp
sdm
prcw
kffib
ncdkd
gee
shvea
lgrdy
sl
xc
lby
up
eefl
epc...

output:

27243835

result:

ok single line: '27243835'