记录编号	593655	评测结果	R
题目名称	[POJ 1417]真正的说谎者	最终得分	0
用户昵称	flyfree	是否通过	未通过
代码语言	C++	运行时间	0.239 s
提交时间	2024-09-06 22:02:51	内存使用	3.12 MiB

#include<bits/stdc++.h>
using namespace std;
#define N 1000
#define int long long
inline int read(){
    int x=0,f=1;
    char c=getchar();
    while(c<'0'||c>'9'){
        if(c=='-')f=-1;
        c=getchar();
    }
    while(c>='0'&&c<='9'){
        x=x*10+c-'0';
        c=getchar();
    }
    return x*f;
}
int n,q,p,idx,g;
int f[2010],s1[2010],s2[2010];//s1恶魔，s2天使 
int dp[2010][2010],fnt[2010][2010],z[2010][2010],mp[2010],used[2010];
int find(int x){
    if(x==f[x])return x;
    else return f[x]=find(f[x]);
}
signed main(){
//    freopen("trueliars.in","r",stdin);
//    freopen("trueliars.out","w",stdout);
    while(1){
        n=read(),p=read(),q=read();
//        cout<<n<<" "<<p<<" "<<q<<endl;
        if(n==0&&p==0&&q==0)return 0;
        g=0;
        memset(dp,0,sizeof(dp));
        memset(fnt,0,sizeof(fnt));
        memset(z,0,sizeof(z));
        memset(mp,0,sizeof(mp));
        memset(s1,0,sizeof(s1));
        memset(s2,0,sizeof(s2));
        memset(used,0,sizeof(used));
        memset(f,0,sizeof(f));
        idx=0;
        for(int i=1;i<=p+q;i++){
            f[N+i]=N+i;
            f[N-i]=N-i;
        }
        for(int i=1;i<=n;i++){
            int l=read(),r=read();
            string s;
            cin>>s;
            if(g)continue;
            if(s=="no"){
                if(l==r)g=1;
                else if(find(l+N)==find(r+N))g=1;
                else{
                    f[find(l+N)]=f[find(N-r)];
                    f[find(N-l)]=f[find(N+r)];
                }
            }else{
                if(find(N+l)==find(N-r))g=1;
                else{
                    f[find(l+N)]=f[find(N+r)];
                    f[find(N-l)]=f[find(N-r)];
                }
            }
        }
        if(g){
            cout<<"no\n";
            continue;
        }
        for(int i=N+1;i<=N+p+q;i++){
            if(i==N)continue;
            int S=find(i);
            if(S<N){
                if(!s1[N-S]&&!s2[N-S])mp[++idx]=N-S;
                s1[N-S]++;
            }else{
                if(!s1[S-N]&&!s2[S-N])mp[++idx]=S-N;
                s2[S-N]++;
            }
        }
        dp[1][0]=1;
        for(int i=1;i<=idx;i++){
//            cout<<mp[i]<<" "<<s1[mp[i]]<<" "<<s2[mp[i]]<<endl;
            int now=mp[i];
            if(g)break;
            if(s1[now]==s2[now]){
                g=1;
                break;
            }
            for(int j=0;j<=q+p;j++){
                if(dp[i][j]){
                    if(s1[now]){
                        if(dp[i+1][j+s1[now]]){
                            g=1;
                            break;
                        }
                        dp[i+1][j+s1[now]]=1;
                        fnt[i+1][j+s1[now]]=j;
                        z[i+1][j+s1[now]]=-1;
                    }
                    if(s2[now]){
                        if(dp[i+1][j+s2[now]]){
                            g=1;
                            break;
                        }
                        dp[i+1][j+s2[now]]=1;
                        fnt[i+1][j+s2[now]]=j;
                        z[i+1][j+s2[now]]=1;
                    }
                }
            }
        }
        if(g){
            cout<<"no\n";
            continue;
        }
        if(p==0){
            cout<<"end\n";
            continue;
        }
        if(!!dp[idx+1][p]){
            cout<<"no\n";
            continue;
        }
        int now=p;
        for(int i=idx+1;i>1;i--){
            if(z[i][now]==1){
                used[N+mp[i-1]]=1;
            }else{
                used[N-mp[i-1]]=1;
            }
            now=fnt[i][now];
        }
        for(int i=N+1;i<=N+p+q;i++){
            int S=find(i);
            if(used[S])cout<<i-N<<endl;
        }
        cout<<"end\n";
    }
    return 0;
}