比赛 |
9.6 |
评测结果 |
W |
题目名称 |
真正的说谎者 |
最终得分 |
0 |
用户昵称 |
健康铀 |
运行时间 |
0.020 s |
代码语言 |
C++ |
内存使用 |
11.14 MiB |
提交时间 |
2024-09-06 21:58:33 |
显示代码纯文本
#include <bits/stdc++.h>
using namespace std;
const long long MAXN = 1005;
long long s[MAXN], r[MAXN], a[MAXN][2], dp[MAXN][MAXN],f[MAXN];
set<long long> ans;
long long find(long long x) {
if (s[x] != x) {
long long t = s[x];
s[x] = find(s[x]);
r[x] =(r[x]+r[t])%2;
}
return s[x];
}
void join(long long x, long long y, long long d) {
long long sx=find(x),sy=find(y);
if (sx!=sy) {
s[sy]=sx;
r[sy]=(r[x]-r[y]+d+2)%2;
}
}
int main() {
freopen("trueliars.in","r",stdin);
freopen("trueliars.out","w",stdout);
ios::sync_with_stdio(false);
cin.tie(0); cout.tie(0);
long long n, p, q;
while (cin >> n >> p >> q && (n | p | q)) {
memset(s, 0, sizeof(s));
memset(r, 0, sizeof(r));
memset(a, 0, sizeof(a));
memset(dp, 0, sizeof(dp));
ans.clear();
for (long long i = 1; i <= p + q; ++i) s[i] = i;
for (long long i = 0; i < n; ++i) {
long long x, y,z=0;
string str;
cin >> x >> y >> str;
if(str[0]=='n')
z=1;
join(x, y, z);
}
long long top=0;
for (long long i = 1; i <= p + q; ++i) {
if (find(i) == i) {
f[++top]=i;
for (long long j = 1; j <= p + q; ++j) {
if (find(j) == i) {
a[top][r[j]]++;
}
}
}
}
dp[0][0] = 1;
for(long long i = 1;i <= top;i++){
for(long long j = p;j >= 0;j--){
if(j >= a[i][0])
dp[i][j] += dp[i-1][j-a[i][0]];
if(j >= a[i][1])
dp[i][j] += dp[i-1][j-a[i][1]];
}
}
if (dp[top][p] != 1) {
cout << "no" << endl;
continue;
}
long long t=p;
for (long long i = top; i >= 1; --i) {
if (dp[i-1][t-a[i][0]] == 1) {
for (long long j = 1; j <= p + q; ++j) {
if (find(j) == f[i] && r[j] == 0) {
ans.insert(j);
}
}
p-=a[i][0];
} else {
for (long long j = 1; j <= p + q; ++j) {
if (find(j) == f[i] && r[j] == 1) {
ans.insert(j);
}
}
p-=a[i][1];
}
}
for(long long x:ans)
cout<<x<<endl;
cout << "end" << endl;
}
return 0;
}