|
|
back to boardRE test#11 why?? #include<cstdio> #include<algorithm> #include<iostream> #include<cmath> #include<climits> #include<string> #include<string.h> #include<vector> #define sf scanf #define pf printf #define cls(a) memset(a,0,sizeof(a)) #define _cls(a) memset(a,-1,sizeof(a)) using namespace std; struct Edge_t{ int to,next; }edge[400000]; int hed[200000]; int et; struct tree{ tree *br[26]; vector<int>vec; tree(){ for(int i=0;i<26;++i) br[i]=NULL; vec.clear(); } }; struct Input{ char str[18]; int val; }inp[100010]; tree *head; inline void adde(int u,int v){ edge[et].to=v,edge[et].next=hed[u],hed[u]=et++; } inline void addtree(char *st,int index){ int id,i; tree *s=head; for(i=0;st[i];++i){ id=st[i]-'a'; if(!s->br[id]) s->br[id]=new tree; s=s->br[id]; } s->vec.push_back(index); } inline bool cmp(int a,int b){ if(inp[a].val==inp[b].val) return strcmp(inp[a].str,inp[b].str)<0; return inp[a].val>inp[b].val; } void DEL(tree *s){ int i; for(i=0;i<26;++i) if(s->br[i]) DEL(s->br[i]); s->vec.clear(); delete(s); } int res[1000010]; void deal(char *st,int index){ int i,id,j; tree *s=head; for(i=0;st[i];++i){ id=st[i]-'a'; if(!s->br[id]) return; s=s->br[id]; for(j=0;j<s->vec.size();++j) adde(s->vec[j],index); } } int main(){ int i,j; int n,m,sk; char str[18]; while(scanf("%d",&n)!=EOF){ head=new tree; _cls(hed); for(i=et=0;i<n;++i) sf("%s%d",inp[i].str,&inp[i].val); sf("%d",&m); for(j=0;j<m;++j){ sf("%s",str); addtree(str,j); } for(i=0;i<n;++i) deal(inp[i].str,i); int e; for(i=0;i<m;++i){ if(i) puts(""); for(sk=0,e=hed[i];e!=-1;e=edge[e].next) res[sk++]=edge[e].to; if(!sk) continue; sort(res,res+sk,cmp); //if(sk>0) for(j=0;j<sk && j<10;++j) pf("%s\n",inp[res[j]].str); } DEL(head); } return 0; } /* 2 ab 10 ac 20 1 f */ |
|
|