比赛 |
9.6 |
评测结果 |
A |
题目名称 |
真正的说谎者 |
最终得分 |
100 |
用户昵称 |
小金 |
运行时间 |
0.009 s |
代码语言 |
C++ |
内存使用 |
5.38 MiB |
提交时间 |
2024-09-06 21:50:21 |
显示代码纯文本
#include<iostream>
#include<cstdio>
#include<vector>
#include<algorithm>
#include<cstring>
using namespace std;
const int maxn=610;
vector<int> pre,ans;
int dp[maxn][maxn],path[maxn][maxn];
int f[maxn],dis[maxn],cnt[maxn][2];
int q,n1,n2;
int find(int p)
{
if(f[p]==p) return p;
int res=find(f[p]);
dis[p]=(dis[p]+dis[f[p]])%2;
f[p]=res;
return res;
}
bool merge(int u,int v,int val)
{
int fu=find(u),fv=find(v);
if(fu!=fv)
{
f[fv]=fu;
dis[fv]=(dis[u]+dis[v]+val)%2;
if(dis[fv])
{
cnt[fu][0]+=cnt[fv][1];
cnt[fu][1]+=cnt[fv][0];
}
else
{
cnt[fu][0]+=cnt[fv][0];
cnt[fu][1]+=cnt[fv][1];
}
return 1;
}
else
{
if((dis[u]-dis[v]+2)%2!=val) return 0;
else return 1;
}
}
int main()
{
freopen("trueliars.in","r",stdin);
freopen("trueliars.out","w",stdout);
bool res,flag;
int u,v;
char ch[10];
while(scanf("%d%d%d",&q,&n1,&n2)!=EOF)
{
if(q==0&&n1==0&&n2==0) break;
for(int i=1;i<=n1+n2;i++)
{
f[i]=i;
dis[i]=0;
cnt[i][0]=1;
cnt[i][1]=0;
}
flag=1;
while(q--)
{
scanf("%d%d%s",&u,&v,ch);
if(!flag) continue;
if(ch[0]=='y') res=merge(u,v,0);
else res=merge(u,v,1);
if(!res) flag=0;
}
if(flag)
{
pre.clear();
pre.push_back(0);
for(int i=1;i<=n1+n2;i++)
{
if(f[i]==i) pre.push_back(i);
}
memset(dp,0,sizeof(dp));
dp[0][0]=1;
for(int i=1;i<=pre.size()-1;i++)
{
for(int j=0;j<=n1;j++)
{
if(j-cnt[pre[i]][0]>=0&&dp[i-1][j-cnt[pre[i]][0]]!=0)
{
dp[i][j]+=dp[i-1][j-cnt[pre[i]][0]];
path[i][j]=0;
}
if(j-cnt[pre[i]][1]>=0&&dp[i-1][j-cnt[pre[i]][1]]!=0)
{
dp[i][j]+=dp[i-1][j-cnt[pre[i]][1]];
path[i][j]=1;
}
}
}
if(dp[pre.size()-1][n1]==1)
{
ans.clear();
int j=n1;
for(int i=pre.size()-1;i>=1;i--)
{
for(int k=1;k<=n1+n2;k++)
{
if(find(k)==pre[i]&&dis[k]==path[i][j]) ans.push_back(k);
}
j-=cnt[pre[i]][path[i][j]];
}
sort(ans.begin(),ans.end());
for(int i=0;i<ans.size();i++)
{
printf("%d\n",ans[i]);
}
printf("end\n");
}
else printf("no\n");
}
else printf("no\n");
}
return 0;
}