Submission #1201404

---

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=123456;
const int INF=1000000009;
 
char C[A]; 
int parent[A],Parent[A],node[A],Node[A],O[26];
int G[A]; P H[A];
int J[A];
int JJ[A];
int Cnt[A];
int table[26][26];
vector<int> ch[A],L[A];
string S[A],T[A],U[A],V[A];
 
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-1;
     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-1) return A-1;
  if(p>=0&&(parent[p]>=0&&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]);
  }
}
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); 
}
 
int main(){
 
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-1);  
 
for(int i = 0; i < I; i++) if(parent[i]>=0) ch[parent[i]].push_back(i);
 
for(int i = 0; i < I; i++){
  int p=parent[i];
  if(p>=0&&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-1); 
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-1) 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-1);
 
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-1);
  printf("%d\n",ans+1);
}
 
return 0;
 
}

Submission Info

Compile Error

./Main.cpp: In function ‘int main()’:
./Main.cpp:94:17: warning: ignoring return value of ‘int scanf(const char*, ...)’, declared with attribute warn_unused_result [-Wunused-result]
   scanf("%s", C);
                 ^
./Main.cpp:157: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