Submission #921507
Source Code Expand
#include <bits/stdc++.h> using namespace std; #define dump(...) cout<<"# "<<#__VA_ARGS__<<'='<<(__VA_ARGS__)<<endl #define repi(i,a,b) for(int i=int(a);i<int(b);i++) #define peri(i,a,b) for(int i=int(b);i-->int(a);) #define rep(i,n) repi(i,0,n) #define per(i,n) peri(i,0,n) #define all(c) begin(c),end(c) #define mp make_pair #define mt make_tuple using uint=unsigned; using ll=long long; using ull=unsigned long long; using vi=vector<int>; using vvi=vector<vi>; using vl=vector<ll>; using vvl=vector<vl>; using vd=vector<double>; using vvd=vector<vd>; using vs=vector<string>; template<typename T1,typename T2> ostream& operator<<(ostream& os,const pair<T1,T2>& p){ return os<<'('<<p.first<<','<<p.second<<')'; } template<typename Tuple> void print_tuple(ostream&,const Tuple&){} template<typename Car,typename... Cdr,typename Tuple> void print_tuple(ostream& os,const Tuple& t){ print_tuple<Cdr...>(os,t); os<<(sizeof...(Cdr)?",":"")<<get<sizeof...(Cdr)>(t); } template<typename... Args> ostream& operator<<(ostream& os,const tuple<Args...>& t){ print_tuple<Args...>(os<<'(',t); return os<<')'; } template<typename Ch,typename Tr,typename C> basic_ostream<Ch,Tr>& operator<<(basic_ostream<Ch,Tr>& os,const C& c){ os<<'['; for(auto i=begin(c);i!=end(c);++i) os<<(i==begin(c)?"":" ")<<*i; return os<<']'; } constexpr int INF=1e9; constexpr int MOD=1e9+7; constexpr double EPS=1e-9; constexpr int ALPHABET=26; int ToInt(char c) { return c-'a'; } char ToChar(int x) { return x+'a'; } struct Node{ char value; shared_ptr<Node> parent; array<shared_ptr<Node>,ALPHABET> children; bool last; int count; Node(char v):value(v),last(false),count(0){} }; struct Patricia{ shared_ptr<Node> root; vector<shared_ptr<Node>> lasts; Patricia():root(make_shared<Node>('!')){} void Add(const string& s){ auto cur=root; for(char c:s){ auto& child=cur->children[ToInt(c)]; if(!child){ child=make_shared<Node>(c); child->parent=cur; } cur=child; cur->count++; } cur->last=true; lasts.push_back(cur); } void Compress(){ for(auto cur:lasts){ while(cur && cur->parent && cur->parent->parent){ auto p=cur->parent,g=p->parent; if(cur->count==p->count){ g->children[ToInt(p->value)]=cur; cur->value=p->value; cur->parent=g; } else cur=p; } } } }; int main() { ios_base::sync_with_stdio(false); cin.tie(nullptr); for(int n;cin>>n && n;){ vs ss(n); rep(i,n) cin>>ss[i]; int q; cin>>q; vi ks(q); vs ps(q); rep(i,q){ cin>>ks[i]>>ps[i]; ks[i]--; } Patricia pt; vector<shared_ptr<Node>> lasts; for(auto s:ss) pt.Add(s); pt.Compress(); rep(_,q){ string p=ps[_]; int res=0; for(auto cur=pt.lasts[ks[_]];cur!=pt.root;cur=cur->parent){ if(cur->last) res++; for(char c:p){ if(c==cur->value) break; if(cur->parent->children[ToInt(c)]) res+=cur->parent->children[ToInt(c)]->count; } } cout<<res<<endl; } } }
Submission Info
Submission Time | |
---|---|
Task | E - Lexicographical disorder |
User | lyoz |
Language | C++14 (GCC 5.4.1) |
Score | 1100 |
Code Size | 3112 Byte |
Status | AC |
Exec Time | 2489 ms |
Memory | 195968 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 | 632 ms | 62192 KB |
02.txt | AC | 628 ms | 62192 KB |
03.txt | AC | 642 ms | 62192 KB |
04.txt | AC | 628 ms | 62192 KB |
05.txt | AC | 749 ms | 149236 KB |
06.txt | AC | 751 ms | 192640 KB |
07.txt | AC | 744 ms | 195328 KB |
08.txt | AC | 728 ms | 195840 KB |
09.txt | AC | 723 ms | 195968 KB |
10.txt | AC | 719 ms | 195792 KB |
11.txt | AC | 591 ms | 24440 KB |
12.txt | AC | 596 ms | 31732 KB |
13.txt | AC | 603 ms | 40180 KB |
14.txt | AC | 768 ms | 183936 KB |
15.txt | AC | 753 ms | 195968 KB |
16.txt | AC | 723 ms | 195792 KB |
17.txt | AC | 722 ms | 195740 KB |
18.txt | AC | 2237 ms | 8960 KB |
19.txt | AC | 2234 ms | 8960 KB |
20.txt | AC | 2472 ms | 9344 KB |
21.txt | AC | 2467 ms | 9344 KB |
22.txt | AC | 2489 ms | 9344 KB |
23.txt | AC | 617 ms | 41716 KB |
24.txt | AC | 604 ms | 24696 KB |
25.txt | AC | 594 ms | 31988 KB |
26.txt | AC | 2035 ms | 8960 KB |
27.txt | AC | 564 ms | 27136 KB |
28.txt | AC | 572 ms | 34688 KB |
29.txt | AC | 550 ms | 33792 KB |
30.txt | AC | 599 ms | 50552 KB |
31.txt | AC | 590 ms | 65664 KB |
32.txt | AC | 550 ms | 46976 KB |
33.txt | AC | 577 ms | 73984 KB |
34.txt | AC | 575 ms | 64640 KB |
35.txt | AC | 585 ms | 83456 KB |
36.txt | AC | 637 ms | 70768 KB |
37.txt | AC | 613 ms | 102036 KB |
38.txt | AC | 619 ms | 102036 KB |
39.txt | AC | 3 ms | 256 KB |
40.txt | AC | 3 ms | 256 KB |
s1.txt | AC | 3 ms | 256 KB |
s2.txt | AC | 3 ms | 256 KB |