QOJ.ac
QOJ
ID | Problem | Submitter | Result | Time | Memory | Language | File size | Submit time | Judge time |
---|---|---|---|---|---|---|---|---|---|
#397218 | #2791. 背单词 | james1BadCreeper | 100 ✓ | 35ms | 48664kb | C++14 | 1.3kb | 2024-04-23 19:45:56 | 2024-04-23 19:45:58 |
Judging History
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'