Submission #1199150

---

Source Code Expand

#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <cmath>
#include <cassert>
#include <iostream>
#include <sstream>
#include <vector>
#include <queue>
#include <set>
#include <map>
#include <utility>
#include <numeric>
#include <algorithm>
#include <bitset>
#include <complex>
#include <array>
#include <list>
#include <stack>
#include <valarray>

using namespace std;

typedef pair<int,string> P;
typedef pair<int,int> PP;
typedef pair<string,int> PPP;
int N,Q,K,X,Y,Max,I,ans;
const int A=400010,B=100010;
const int INF=1000000009;

char C[A]; 
int parent[A],Parent[A],node[A],Node[A],O[30];
int G[B]; PPP H[B];
int J[B];
int JJ[B];
vector<int> ch[A],L[A];
string S[B],T[B],U[B],V[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;
  	 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(ch[parent[p]].size()==1){
		return Pr(p);
	}else{
		return p;
	}
}

void order(int k){
  if(L[k].size()==0){
 	return;
  }
	vector<PP> o;
  for(int i=0; i<L[k].size(); i++){
  	if(node[L[k][i]]==-INF) o.push_back(PP(-INF,L[k][i]));
  	else{
  	 int w=O[node[L[k][i]]];
  	 o.push_back(PP(w,L[k][i]));
    }
  }
  	
  sort(o.begin(),o.end());

  for(int j=0; j<o.size(); j++){
  	if(j==0) Y--;
  	Node[o[j].second]=Y; Y++;
  	order(o[j].second);
  }
  return;
}

void make(int k){
  if(L[k].size()==0){
  	//cout<<k<<endl;
  	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,int j){
  if(L[k].size()==0){
  	ans=Node[k]; 
  	return;
  }
  for(int i=0; i<L[k].size(); i++){
  	 if(V[G[K-1]][j]-'a'==node[L[k][i]]){
  	 	 Find(L[k][i],j+1); 
  	 }
  }
}

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(ch[p].size()==1&&p>=0) 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);
}

//cout<<L[A-1][1]<<endl;

make(A-1); 
for(int i=0; i<N; i++){
  if(J[i]>=0){
  	char c='a'+J[i];
  	V[i]=c;
  }else{
  	V[i]="";
  }
  //cout<<V[i]<<endl;
  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); 
/*V[0]="aa"; //aa
V[1]="aba"; //abbaa
V[2]="abb"; //abbba
V[3]="aaab"; //aaab
V[4]="aaaa";*/ //aaaaaba 
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;
}

/*for(int i=0; i<N; i++){
	cout<<V[i]<<endl;
	}*/

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++){
	T[i][j]-'a';
	O[T[i][j]-'a']=j;
    }
    X=0; 
    Y=1; 
    I=0;  
    order(A-1); 
    Find(A-1,0);
	printf("%d\n",ans+1);
}

//cout<<Node[22]<<endl;

return 0;
 
}

Submission Info

Compile Error

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

Judge Result