竞赛讨论区 > J - 解压文本 通过率70%……What?

J - 解压文本 通过率70%……What?

//#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) 回帖
加载中...
话题 回帖

等你来战

查看全部

热门推荐