Submission #921511
Source Code Expand
#include <bits/stdc++.h> using namespace std; struct pnt{ pnt * alp[26]; bool exist[26]; int sz, dist; bool is_end; pnt(){ sz=0; is_end=0; dist=1; for(int i=0; i<26; ++i){ exist[i]=0; } } } * root; string a[100010]; void ins(int x){ pnt * p = root; ++(p->sz); int chr; for(int i=0; i<a[x].size(); ++i){ chr=a[x][i]-'a'; if(!(p->exist[chr])){ p->alp[chr]=new pnt(); p->exist[chr]=1; } p=p->alp[chr]; ++(p->sz); } p->is_end=1; } int ans, k; string alphabet; void qry(){ pnt * p =root; ans=0; int ch; for(int i=0; i<a[k].size(); ++i){ if(p->is_end) ++ans; for(int j=0; j<26; ++j){ ch=alphabet[j]-'a'; if(alphabet[j]==a[k][i]){ i+=(p->dist)-1; p=p->alp[ch]; break; } if((p->exist[ch])) ans+=(p->alp[ch])->sz; } } } int simplify1(pnt * p){ for(int i=0; i<26; ++i){ if((p->exist[i])){ if(p->sz==p->alp[i]->sz){ p->dist = 1+simplify1(p->alp[i]); return p->dist; } else{ simplify1(p->alp[i]); } } } return 0; } pnt* simplify2(pnt * p){ for(int i=0; i<26; ++i){ if((p->exist[i])){ if(p->sz==p->alp[i]->sz){ p->alp[i] = simplify2(p->alp[i]); return p->alp[i]; } else{ simplify2(p->alp[i]); } } } return p; } int main(){ int n, q; root = new pnt(); cin>>n; for(int i=1; i<=n; ++i){ cin>>a[i]; ins(i); } simplify1(root); simplify2(root); cin>>q; for(int i=0; i<q; ++i){ cin>>k>>alphabet; qry(); cout<<ans+1<<endl; } return 0; }
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | Zain |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 1747 Byte |
Status | AC |
Exec Time | 3047 ms |
Memory | 114052 KB |
Judge Result
Set Name | Sample | All | ||||
---|---|---|---|---|---|---|
Score / Max Score | 0 / 0 | 1100 / 1100 | ||||
Status |
|
|
Set Name | Test Cases |
---|---|
Sample | s1.txt, s2.txt |
All | 01.txt, 02.txt, 03.txt, 04.txt, 05.txt, 06.txt, 07.txt, 08.txt, 09.txt, 10.txt, 11.txt, 12.txt, 13.txt, 14.txt, 15.txt, 16.txt, 17.txt, 18.txt, 19.txt, 20.txt, 21.txt, 22.txt, 23.txt, 24.txt, 25.txt, 26.txt, 27.txt, 28.txt, 29.txt, 30.txt, 31.txt, 32.txt, 33.txt, 34.txt, 35.txt, 36.txt, 37.txt, 38.txt, 39.txt, 40.txt, s1.txt, s2.txt |
Case Name | Status | Exec Time | Memory |
---|---|---|---|
01.txt | AC | 730 ms | 31232 KB |
02.txt | AC | 732 ms | 31232 KB |
03.txt | AC | 728 ms | 31232 KB |
04.txt | AC | 728 ms | 31232 KB |
05.txt | AC | 812 ms | 77824 KB |
06.txt | AC | 772 ms | 100224 KB |
07.txt | AC | 755 ms | 101632 KB |
08.txt | AC | 758 ms | 101760 KB |
09.txt | AC | 747 ms | 102144 KB |
10.txt | AC | 744 ms | 104704 KB |
11.txt | AC | 701 ms | 11008 KB |
12.txt | AC | 698 ms | 15104 KB |
13.txt | AC | 697 ms | 19200 KB |
14.txt | AC | 792 ms | 95488 KB |
15.txt | AC | 763 ms | 102016 KB |
16.txt | AC | 747 ms | 104704 KB |
17.txt | AC | 742 ms | 114052 KB |
18.txt | AC | 2539 ms | 2304 KB |
19.txt | AC | 2573 ms | 2304 KB |
20.txt | AC | 3047 ms | 2432 KB |
21.txt | AC | 2902 ms | 2432 KB |
22.txt | AC | 2896 ms | 2432 KB |
23.txt | AC | 735 ms | 20480 KB |
24.txt | AC | 709 ms | 11136 KB |
25.txt | AC | 707 ms | 15232 KB |
26.txt | AC | 2440 ms | 2304 KB |
27.txt | AC | 725 ms | 11904 KB |
28.txt | AC | 724 ms | 16128 KB |
29.txt | AC | 694 ms | 15488 KB |
30.txt | AC | 720 ms | 24704 KB |
31.txt | AC | 684 ms | 32512 KB |
32.txt | AC | 669 ms | 22656 KB |
33.txt | AC | 666 ms | 38272 KB |
34.txt | AC | 662 ms | 32640 KB |
35.txt | AC | 676 ms | 42240 KB |
36.txt | AC | 740 ms | 35840 KB |
37.txt | AC | 669 ms | 57992 KB |
38.txt | AC | 673 ms | 57992 KB |
39.txt | AC | 3 ms | 1024 KB |
40.txt | AC | 3 ms | 1024 KB |
s1.txt | AC | 3 ms | 1024 KB |
s2.txt | AC | 3 ms | 1024 KB |