比赛 9.6 评测结果 A
题目名称 真正的说谎者 最终得分 100
用户昵称 wdsjl 运行时间 0.011 s
代码语言 C++ 内存使用 6.45 MiB
提交时间 2024-09-06 21:46:20
显示代码纯文本
#include <bits/stdc++.h>
const int MAXN = 610;
using namespace std;

int p[MAXN],rk[MAXN],gg[MAXN],jj[MAXN][MAXN],tag[MAXN][2],dp[MAXN][MAXN],cc[MAXN][2];

int find(int x){
    if(x!=p[x]){
        int px=find(p[x]);
        rk[x]^=rk[p[x]];
        p[x]=px;
    }
    return p[x];
}

void merge(int x, int y, int d){
    int px=find(x);
    int py=find(y);
    if(px!=py){
        p[py]=px;
        rk[py]=rk[x]^rk[y]^d;
    }
}

int main(){
	freopen("trueliars.in","r",stdin);
	freopen("trueliars.out","w",stdout);
    int m,pi,q;
    while(scanf("%d%d%d",&m,&pi,&q)){
        if(m+pi+q==0){
            break;
        }
        for(int i=1;i<=pi+q;i++){ 
            rk[i]=0;
            p[i]=i;
        }
        while(m--){
            int x,y,d=1;
            char ch[5];
            scanf("%d%d%s",&x,&y,ch);
            if(ch[0]=='y'){
                d=0;
            }
            merge(x,y,d);
        }
        memset(gg,0,sizeof(gg)); 
        memset(jj,0,sizeof(jj));
        memset(tag,0,sizeof(tag));
        memset(dp,0,sizeof(dp));
        memset(cc,0,sizeof(cc));
        int tot=0;
        for(int i=1;i<=pi+q;i++){ 
            if(find(i)==i){
                gg[i]=++tot;
            }
        }
        for(int i=1;i<=pi+q;i++){  
            tag[gg[find(i)]][rk[i]]++;
        }
        dp[0][0]=1;
        for(int i=1;i<=tot;i++){
            for(int j=0;j<=pi+q;j++){  
                if(j-tag[i][0]>=0&&dp[i-1][j-tag[i][0]]){
                    dp[i][j]+=dp[i-1][j-tag[i][0]];
                    jj[i][j]=tag[i][0];   
                }
                if(j-tag[i][1]>=0&&dp[i-1][j-tag[i][1]]){
                    dp[i][j]+=dp[i-1][j-tag[i][1]];
                    jj[i][j]=tag[i][1];
                }
            }
        }
        if(dp[tot][pi]!=1){
            printf("no\n");
        }else{
            for(int i=tot,j=pi;j>0&&i>0;i--){ 
                if(jj[i][j]==tag[i][0]){
                    cc[i][0]=1;
                }else{
                    cc[i][1]=1;
                }
                j-=jj[i][j];
            }
            for(int i=1;i<=pi+q;i++){
                if(cc[gg[find(i)]][rk[i]]){
                    printf("%d\n",i);
                }
            }
            printf("end\n");
        }
    }
    return 0;
}