比赛 |
9.6 |
评测结果 |
W |
题目名称 |
真正的说谎者 |
最终得分 |
0 |
用户昵称 |
flyfree |
运行时间 |
0.122 s |
代码语言 |
C++ |
内存使用 |
49.73 MiB |
提交时间 |
2024-09-06 21:03:12 |
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
#define N 1000
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]);
}
int 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));
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||!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;
}