Submission #1199120
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,index,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<<" "<<index++<<" "<<p<<endl; node[index]=x; if(j==0) parent[index]=A-1; else parent[index]=p; index++; if(x<0) return; if(j<Max) dfs(k,e,j+1,index-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 < index; i++){ if(parent[i]>=0) ch[parent[i]].push_back(i); } for(int i = 0; i < index; i++){ int p=parent[i]; if(ch[p].size()==1&&p>=0) node[i]=-INF; } for(int i = 0; i < index; i++){ if(node[i]>-INF){ Parent[i]=Pr(i); }else{ Parent[i]=-INF; } } for(int i = 0; i < index; 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; index=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 | 3268 Byte |
Status | CE |
Compile Error
./Main.cpp:8:19: error: ‘int index’ redeclared as different kind of symbol int N,Q,K,X,Y,Max,index,ans; ^ In file included from /usr/include/c++/5/cstring:42:0, from /usr/include/x86_64-linux-gnu/c++/5/bits/stdc++.h:48, from ./Main.cpp:1: /usr/include/string.h:482:1: note: previous declaration ‘const char* index(const char*, int)’ index (const char *__s, int __c) __THROW ^ ./Main.cpp: In function ‘void dfs(int, int, int, int)’: ./Main.cpp:29:15: error: invalid types ‘int [400010][<unresolved overloaded function type>]’ for array subscript node[index]=x; ^ ./Main.cpp:30:26: error: invalid types ‘int [400010][<unresolved overloaded function type>]’ for array subscript if(j==0) parent[index]=A-1; ^ ./Main.cpp:31:22: error: invalid types ‘int [400010][<unresolved overloaded function type>]’ for array subscript else parent[index]=p; ^ ./Main.cpp:32:10: error: no post-increment o...