Submission #1202110


Source Code Expand

#include <bits/stdc++.h>
 
using namespace std;
 
typedef pair<string,int> P;
int N,Q,K,X,Y,W,Max,I,ans;
const int A=777777,B=223456;
const int INF=1000000009;
 
char C[A]; 
int parent[A],Parent[A],node[A],Node[A],O[30];
int G[B]; P H[B];
int J[B];
int JJ[A];
int Cnt[A];
int table[30][30]; 
vector<int> ch[A],L[A];
string S[B],T[B],U[B],V[B],R[B];
 
void dfs(int s,int e,int j,int p){
    int x=S[s][j]-'a'; int k=s;
  for(int i=s; i<=e; i++){
    if(x!=S[i][j]-'a'){
      dfs(k,i-1,j,p); k=i;
      x=S[i][j]-'a'; 
    }
  }
     //cout<<x<<" "<<j<<" "<<I++<<" "<<p<<endl;
     if(x<0) node[I]=26;
     else node[I]=x;
     if(j==0) parent[I]=A-10;
     else parent[I]=p;
     I++;
    if(x<0) return;
    if(j<Max) dfs(k,e,j+1,I-1);
    return;
}
int Pr(int k){
  int p=parent[k];
  if(p==A-10) return A-10;
  if(ch[parent[p]].size()==1){
    return Pr(p);
  }else{
    return p;
  }
}
int cnt(int k){
  if(L[k].size()==0){
    Cnt[k]=1;
    return 1;
  }
  for(int i=0; i<L[k].size(); i++){
    Cnt[k]+=cnt(L[k][i]);
  }
    return Cnt[k];
}
void make(int k){
  if(L[k].size()==0){
    J[X]=node[k]; JJ[X]=k;
    X++;
    return;
  }
  for(int i=0; i<L[k].size(); i++){
    make(L[k][i]);
  }
  return;
}
void Find(int k){
  if(W>=V[G[K-1]].size()) return;
  if(L[k].size()==0) return;
  int s;
  if(V[G[K-1]][W]-'a'>=0) s=V[G[K-1]][W]-'a'; 
  else s=-INF;
  int t;
  for(int i=0; i<L[k].size(); i++){
     if(s==node[L[k][i]]){
      t=L[k][i]; 
     }
     if(node[L[k][i]]<26&&table[s][node[L[k][i]]]==0){
      ans+=Cnt[L[k][i]];
     }
     if(node[L[k][i]]==26){
      ans++;
      Find(L[k][i]); 
     }
  }
  W++; Find(t); 
  return;
}
 
int main(){

ios_base::sync_with_stdio(0); cin.tie(0); cout.tie(0);
 
cin>>N;
 
for(int i = 0; i < N; i++){
  scanf("%s", C);
  S[i] = string(C);
  if(S[i].size()>Max) Max=S[i].size();
}
 
for(int i = 0; i < N; i++) U[i]=S[i];
 
sort(S,S+N);
 
dfs(0,N-1,0,A-10);  
 
for(int i = 0; i < I; i++) ch[parent[i]].push_back(i);
 
for(int i = 0; i < I; i++){
  int p=parent[i];
  if(ch[p].size()==1) node[i]=-INF;
}
 
for(int i = 0; i < I; i++){
  if(node[i]!=-INF){
    Parent[i]=Pr(i);
  }else{
    Parent[i]=-INF;
  }
}
 
for(int i = 0; i < I; i++){
  if(Parent[i]>=0) L[Parent[i]].push_back(i);
}
 
make(A-10); 
for(int i=0; i<N; i++){
  if(J[i]<=25){
    char c='a'+J[i];
    V[i]=c;
  }
  if(J[i]==26){
    V[i]="";
  }
  int k=JJ[i];
  while(1){
    if(Parent[k]==A-10) break;
    char c='a'+node[Parent[k]];
    V[i]=c+V[i];
    k=Parent[k];
  }
}
 
sort(V,V+N); 
for(int i=0; i<N; i++){
  H[i].first=U[i];
  H[i].second=i;
}
sort(H,H+N);
for(int i=0; i<N; i++){
  G[H[i].second]=i;
}
 
cnt(A-10);
 
cin>>Q;
 
for(int i=0; i<Q; i++){
  scanf("%d %s",&K,C);
  T[i] = string(C);
  for(int j=0; j<26; j++){
    O[T[i][j]-'a']=j;
  }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
    table[k][j]=0;
  }
 }
 for(int k=0; k<26; k++){
  for(int j=0; j<26; j++){
   if(O[k]<=O[j]){
    table[k][j]=1;
   }else{
    table[k][j]=0;
   }
  }
 }
  X=0; I=0; ans=0; W=0;
  Find(A-10);
  printf("%d\n",ans+1);
}

//cout<<L[A-1].size()<<endl;
/*for(int i=0; i<N; i++){
  cout<<V[i]<<endl;
}*/
 
return 0;
 
}

Submission Info

Submission Time
Task E - Lexicographical disorder
User momotaro1303
Language C++14 (GCC 5.4.1)
Score 0
Code Size 3343 Byte
Status RE
Exec Time 242 ms
Memory 83328 KB

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:98:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", C);
                 ^
./Main.cpp:161:22: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%d %s",&K,C);
                      ^

Judge Result

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
RE × 2
WA × 37
RE × 5
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 WA 238 ms 80768 KB
02.txt WA 238 ms 80768 KB
03.txt WA 239 ms 80768 KB
04.txt WA 242 ms 80768 KB
05.txt WA 116 ms 79360 KB
06.txt WA 56 ms 77184 KB
07.txt WA 51 ms 76928 KB
08.txt WA 50 ms 76800 KB
09.txt WA 49 ms 76800 KB
10.txt WA 49 ms 76800 KB
11.txt WA 114 ms 67840 KB
12.txt WA 140 ms 70272 KB
13.txt WA 168 ms 73216 KB
14.txt WA 58 ms 76544 KB
15.txt WA 49 ms 76928 KB
16.txt WA 49 ms 76800 KB
17.txt RE 132 ms 77184 KB
18.txt WA 59 ms 63104 KB
19.txt WA 59 ms 63104 KB
20.txt WA 56 ms 63104 KB
21.txt WA 56 ms 63104 KB
22.txt WA 57 ms 63104 KB
23.txt WA 127 ms 70400 KB
24.txt WA 114 ms 67712 KB
25.txt WA 139 ms 70144 KB
26.txt WA 51 ms 62976 KB
27.txt WA 35 ms 64256 KB
28.txt WA 40 ms 65024 KB
29.txt WA 28 ms 64256 KB
30.txt WA 71 ms 67840 KB
31.txt WA 33 ms 66432 KB
32.txt WA 29 ms 65152 KB
33.txt WA 33 ms 67200 KB
34.txt WA 32 ms 66304 KB
35.txt WA 34 ms 67712 KB
36.txt WA 211 ms 83328 KB
37.txt WA 47 ms 76928 KB
38.txt WA 47 ms 76928 KB
39.txt RE 110 ms 61696 KB
40.txt RE 112 ms 61696 KB
s1.txt RE 111 ms 61696 KB
s2.txt RE 112 ms 61696 KB