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