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