Submission #921505
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;
}
}
}
void Dump(shared_ptr<Node> cur,int depth){
int cnt=0;
rep(i,ALPHABET) if(cur->children[i]){
if(cnt++) cout<<endl<<string(depth*4,' ');
cout<<cur->children[i]->value<<'('<<cur->children[i]->count<<')';
Dump(cur->children[i],depth+1);
}
}
void Dump(){
Dump(root,0);
cout<<endl;
}
};
int main()
{
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]--;
}
//dump(mt(n,q));
//dump(ss); dump(ks); dump(ps);
Patricia pt;
vector<shared_ptr<Node>> lasts;
for(auto s:ss) pt.Add(s);
//pt.Dump();
pt.Compress();
//pt.Dump();
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;
}
}
//shared_ptr<Node> cur=pt.root;
//int res=0;
//rep(i,s.size()){
// if(cur->last)
// res++;
// for(char c:p){
// if(s[i]==c) break;
// if(cur->children[ToInt(c)])
// res+=cur->children[ToInt(c)]->count;
// }
// cur=cur->children[ToInt(s[i])];
//}
cout<<res<<endl;
}
}
}
Submission Info
Submission Time |
|
Task |
E - Lexicographical disorder |
User |
lyoz |
Language |
C++14 (GCC 5.4.1) |
Score |
1100 |
Code Size |
3755 Byte |
Status |
AC |
Exec Time |
2577 ms |
Memory |
197632 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 |
790 ms |
63728 KB |
02.txt |
AC |
786 ms |
63728 KB |
03.txt |
AC |
784 ms |
63728 KB |
04.txt |
AC |
804 ms |
63728 KB |
05.txt |
AC |
919 ms |
151412 KB |
06.txt |
AC |
912 ms |
194304 KB |
07.txt |
AC |
892 ms |
196992 KB |
08.txt |
AC |
879 ms |
197376 KB |
09.txt |
AC |
868 ms |
197632 KB |
10.txt |
AC |
858 ms |
197376 KB |
11.txt |
AC |
761 ms |
26488 KB |
12.txt |
AC |
733 ms |
33908 KB |
13.txt |
AC |
746 ms |
41716 KB |
14.txt |
AC |
910 ms |
185472 KB |
15.txt |
AC |
896 ms |
197504 KB |
16.txt |
AC |
871 ms |
197376 KB |
17.txt |
AC |
854 ms |
197380 KB |
18.txt |
AC |
2267 ms |
10624 KB |
19.txt |
AC |
2249 ms |
10624 KB |
20.txt |
AC |
2577 ms |
11008 KB |
21.txt |
AC |
2478 ms |
11008 KB |
22.txt |
AC |
2489 ms |
11008 KB |
23.txt |
AC |
766 ms |
43892 KB |
24.txt |
AC |
734 ms |
26744 KB |
25.txt |
AC |
741 ms |
34164 KB |
26.txt |
AC |
2029 ms |
10624 KB |
27.txt |
AC |
711 ms |
28800 KB |
28.txt |
AC |
707 ms |
36480 KB |
29.txt |
AC |
701 ms |
35456 KB |
30.txt |
AC |
749 ms |
52344 KB |
31.txt |
AC |
729 ms |
67328 KB |
32.txt |
AC |
688 ms |
48512 KB |
33.txt |
AC |
722 ms |
75520 KB |
34.txt |
AC |
707 ms |
66176 KB |
35.txt |
AC |
726 ms |
84992 KB |
36.txt |
AC |
798 ms |
72304 KB |
37.txt |
AC |
758 ms |
103560 KB |
38.txt |
AC |
747 ms |
103560 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 |