//#define DEBUG #include<cstdio> #include<cstring> #include<cctype> #include<string> #include<queue> #define MAX ((int)1e6) #define LEN 10 using std::queue; using std::string; int n,in[LEN],t[LEN],k; bool g[LEN][LEN]; string s[LEN]; inline void read(int x){ string& s=::s[x]; int ch; while(ch=getchar()!='\n'); ch=getchar(); while(ch!='#'){ s+=ch; if(ch=='*'){ ch=getchar(); s+=ch; ch^='0'; if(!g[x][ch]){ ++in[ch]; g[x][ch]=1; } } ch=getchar(); } return; } inline bool topo(){ int u; k=0; queue<int> q; for(int i=1;i<=n;++i) if(!in[i]) q.push(i); while(!q.empty()){ u=q.front(); q.pop(); t[k++]=u; for(int v=1;v<=n;++v) if(g[u][v]){ if(!--in[v]) q.push(v); } } return k==n; } inline bool uncompress(int x){ char res[MAX+1]; int now,k=0; for(int i=0;i<s[x].size();++i){ if(s[x][i]!='*'){ res[k++]=s[x][i]; if(k>MAX) return 0; continue; } now=s[x][++i]^'0'; for(int j=0;j<s[now].size();++j){ res[k++]=s[now][j]; if(k>MAX) return 0; } } res[k]=0; s[x]=string(res); return 1; } int main(){ memset(g,0,sizeof(g)); memset(in,0,sizeof(in)); scanf("%d",&n); for(int i=1;i<=n;++i) read(i); #ifdef DEBUG //return 0; #endif if(!topo()){ Error: #ifdef DEBUG printf("k=%d\n",k); for(int i=0;i<k;++i){ printf("t[%d]=%d ",i,t[i]); if(i==k-1) putchar('\n'); } #endif puts("#"); return 0; } #ifdef DEBUG //return 0; for(int i=0;i<k;++i){ printf("t[%d]=%d ",i,t[i]); if(i==k-1) putchar('\n'); } #endif for(int i=k-1;i>=0;--i) if(!uncompress(t[i])) goto Error; puts(s[1].c_str()); return 0; }
全部评论
(0) 回帖