比赛 |
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;
}