Submission #1199279


Source Code Expand

#include <bits/stdc++.h>

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]]<0) o.push_back(PP(node[L[k][i]],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++) 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);
}

//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

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

Compile Error

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

Set Name Sample All
Score / Max Score 0 / 0 0 / 1100
Status
AC × 2
AC × 14
TLE × 25
RE × 3
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 TLE 6305 ms 49536 KB
02.txt TLE 6305 ms 49536 KB
03.txt TLE 6305 ms 49536 KB
04.txt TLE 6305 ms 49536 KB
05.txt TLE 6304 ms 46592 KB
06.txt TLE 6304 ms 46336 KB
07.txt TLE 6305 ms 50432 KB
08.txt AC 1301 ms 50944 KB
09.txt RE 125 ms 44544 KB
10.txt AC 103 ms 50944 KB
11.txt TLE 6304 ms 36992 KB
12.txt TLE 6304 ms 39296 KB
13.txt TLE 6304 ms 42240 KB
14.txt TLE 6304 ms 45184 KB
15.txt AC 891 ms 51200 KB
16.txt AC 118 ms 50944 KB
17.txt RE 127 ms 44800 KB
18.txt TLE 6304 ms 36608 KB
19.txt TLE 6304 ms 36736 KB
20.txt TLE 6304 ms 36352 KB
21.txt TLE 6304 ms 36352 KB
22.txt TLE 6304 ms 36352 KB
23.txt TLE 6304 ms 39424 KB
24.txt TLE 6304 ms 36992 KB
25.txt TLE 6304 ms 39296 KB
26.txt TLE 6304 ms 36736 KB
27.txt TLE 6304 ms 34816 KB
28.txt TLE 6304 ms 35200 KB
29.txt AC 4644 ms 40064 KB
30.txt TLE 6304 ms 37376 KB
31.txt TLE 6304 ms 40704 KB
32.txt AC 734 ms 40960 KB
33.txt AC 183 ms 42624 KB
34.txt AC 269 ms 41984 KB
35.txt AC 340 ms 43264 KB
36.txt TLE 6305 ms 50048 KB
37.txt AC 81 ms 44672 KB
38.txt AC 82 ms 44672 KB
39.txt AC 11 ms 30976 KB
40.txt RE 104 ms 30976 KB
s1.txt AC 11 ms 30976 KB
s2.txt AC 11 ms 30976 KB