比赛 |
9.6 |
评测结果 |
A |
题目名称 |
真正的说谎者 |
最终得分 |
100 |
用户昵称 |
darkMoon |
运行时间 |
0.149 s |
代码语言 |
C++ |
内存使用 |
65.04 MiB |
提交时间 |
2024-09-06 21:10:40 |
显示代码纯文本
#include<bits/stdc++.h>
#define int long long
using namespace std;
auto IN = freopen("trueliars.in", "r", stdin);
auto OUT = freopen("trueliars.out", "w", stdout);
auto mread = [](){int x;scanf("%lld", &x);return x;};
const int N = 2005;
int m, p, q, fa[N], belong[N], now, s[N][N], f[N][N];
vector<int> v1[N], v2[N];
int findfa(int x){
if(x == fa[x]){
return x;
}
return fa[x] = findfa(fa[x]);
}
bool add(int x, int y){
if(findfa(x) == findfa(y)){
return 1;
}
fa[findfa(x)] = findfa(y);
return 0;
}
signed main(){
while(1){
memset(belong, 0, sizeof(belong));
memset(s, 0, sizeof(s));
memset(f, 0, sizeof(f));
for(int i = 1; i <= now; i ++){
v1[i].clear();
v2[i].clear();
}
now = 0;
cin >> m >> p >> q;
if(m == 0 && p == 0 && q == 0){
return 0;
}
int n = p + q;
for(int i = 1; i <= n + n; i ++){
fa[i] = i;
}
int E = 0;
for(int i = 1; i <= m; i ++){
int x = mread(), y = mread();
string s;
cin >> s;
if(s[0] == 'n'){
if(add(x, y + n)){
1 + 1 == 2;
}
if(add(x + n, y)){
1 + 1 == 2;
}
}
else{
if(add(x, y)){
1 + 1 == 2;
}
if(add(x + n, y + n)){
1 + 1 == 2;
}
}
}
for(int i = 1; i <= n; i ++){
if(findfa(i) == findfa(i + n)){
E = 1;
break;
}
}
if(E){
printf("no\n");
continue;
}
for(int i = 1; i <= n + n; i ++){
fa[i] = findfa(fa[i]);
}
for(int i = 1; i <= n; i ++){
if(belong[i]){
continue;
}
now ++;
for(int j = i; j <= n; j ++){
if(fa[j] == fa[i] || fa[j + n] == fa[i]){
belong[j] = now;
if(fa[j] == fa[i]){
v1[now].push_back(j);
}
else{
v2[now].push_back(j);
}
}
}
}
// printf("\n");
// for(int i = 1; i <= now; i ++){
// printf("*** %lld %lld %lld\n", i, v1[i].size(), v2[i].size());
// }
s[0][0] = 1;
// s[i][j] 表示前 i 组人,有 j 个人是好人
for(int i = 1; i <= now; i ++){
for(int j = 0; j <= n; j ++){
if(j >= v1[i].size()){
if(s[i - 1][j - v1[i].size()] > 0){
s[i][j] += s[i - 1][j - v1[i].size()];
f[i][j] = 1;
}
}
if(j >= v2[i].size()){
if(s[i - 1][j - v2[i].size()] > 0){
s[i][j] += s[i - 1][j - v2[i].size()];
f[i][j] = 2;
}
}
}
}
// printf("--- %lld\n", p);
if(f[now][p]){
if(s[now][p] == 1){
set<int> se;
for(int i = now; i >= 1; i --){
if(f[i][p] == 1){
for(int x : v1[i]){
se.insert(x);
p --;
}
}
else{
for(int x : v2[i]){
se.insert(x);
p --;
}
}
}
for(auto x : se){
printf("%lld\n", x);
}
printf("end\n");
}
else{
printf("no\n");
}
}
else{
printf("no\n");
}
}
return 0;
}