记录编号	593770	评测结果	R
题目名称	[POJ 1417]真正的说谎者	最终得分	0
用户昵称	郑霁桓	是否通过	未通过
代码语言	C++	运行时间	0.003 s
提交时间	2024-09-12 22:00:30	内存使用	3.39 MiB

#include<bits/stdc++.h>
using namespace std;
long long n,m,q,x,y,fa[605],s[605],aa,a[605],ss[605][2];
long long dp[605][605],ps[605][605],pp,vp[605][605];
string p;
long long f(long long x){
    if(fa[x]!=x){
        long long p;
        p=f(fa[x]);
        if(fa[fa[x]]!=fa[x]){
            s[x]^=s[fa[x]];
        }
        fa[x]=p;
    }
    return fa[x];
}
long long ff(long long x){
    if(fa[x]!=x){
        fa[x]=f(fa[x]);
    }
    return fa[x];
}
int main(){
    freopen("td.in","r",stdin);
    freopen("td.out","w",stdout);
    while(1){
    cin>>n>>m>>q;
    for(int i=1;i<=m+q;i++){
        fa[i]=i;
        s[i]=a[i]=0;
    }
    if(!n&&!m&&!q){
        return 0;
    }
    for(int i=1;i<=n;i++){
        cin>>x>>y>>p;
        if(f(x)==f(y)){
            continue;
        }
        if(p[0]=='n'){
            s[f(x)]=1;
        }else{
            s[f(x)]=0;
        }
        fa[f(x)]=y;
    }
    aa=0;
    for(int i=1;i<=m+q;i++){
        f(i);
        if(fa[i]!=i){
            s[i]^=s[fa[i]];
        }
        if(f(i)==i){
            a[f(i)]=++aa;
        }
    }
    for(int i=1;i<=m+q;i++){
        for(int j=0;j<=m+q;j++){
            ss[i][j]=0;
        }
    }    
    memset(dp,0,sizeof(dp));
    memset(ps,0,sizeof(ps));
    for(int i=1;i<=m+q;i++){
        ss[a[ff(i)]][s[i]]++;
        for(int j=0;j<=m+q;j++){
            dp[i][j]=ps[i][j]=vp[i][j]=0;
        }
    }
    
    dp[0][0]=1;
    for(int i=1;i<=aa;i++){
        for(int j=0;j<=m+q;j++){
            if(j>=ss[i][0]&&dp[i-1][j-ss[i][0]]){
                dp[i][j]+=dp[i-1][j-ss[i][0]];
                ps[i][j]=ss[i][0];
            }
            if(j>=ss[i][1]&&dp[i-1][j-ss[i][1]]){
                dp[i][j]+=dp[i-1][j-ss[i][1]];
                ps[i][j]=ss[i][1];
            }
        }
    }
    if(dp[aa][m]!=1){
        cout<<"no\n";
        continue;
    }
    pp=m;
    for(int i=aa;i>=1;i--){
        if(ps[i][pp]==ss[i][0]){
           vp[i][0]=1; 
        }else{
            vp[i][1]=1;
        }
        pp-=ps[i][pp];
    }
    for(int i=1;i<=m+q;i++){
        if(vp[a[f(i)]][s[i]]){
            cout<<i<<"\n";
        }
    }
    cout<<"end\n";
    }
    return 0;
}