比赛 9.6 评测结果 W
题目名称 真正的说谎者 最终得分 0
用户昵称 郑霁桓 运行时间 0.010 s
代码语言 C++ 内存使用 3.49 MiB
提交时间 2024-09-06 21:53:27
显示代码纯文本
#include<bits/stdc++.h>
using namespace std;
long long m,p,q,fa[2005],x,y,pp,tp,pi,pj,aa;
long long hx,hy,sx,sy,t,pt,sz[2005],ps,a[2005];
string s;
long long f(long long x){
    if(fa[x]!=x){
        fa[x]=f(fa[x]);
    }
    return fa[x];
}
map<int,int>mp,mpp,mmp;
map<long long,int>mmpp;
vector<long long>v[605];
int main(){
    freopen("trueliars.in","r",stdin);
    freopen("trueliars.out","w",stdout);
    while(cin>>m>>p>>q){
        mp.clear();
        mpp.clear();
        mmp.clear(); 
        t++;
        pp=tp=hx=hy=sx=sy=pt=ps=aa=0;
        if(!m&&!p&&!q){
            return 0;
        }
        for(int i=1;i<=p+q+p+q;i++){
            fa[i]=i;
        }
        if(p==q){
            while(m--){
                cin>>x>>y>>s;
            }
            cout<<"no\n";
            continue;
        }
        while(m--){
            cin>>x>>y>>s;
            if(s[0]=='n'){
                if(f(x)==f(y)||f(x+p+q)==f(y+p+q)){
                    cout<<"no\n";
                    tp=1;
                    break;
                }
                fa[f(x)]=f(y+p+q);
                fa[f(y)]=f(x+p+q);
            }else{
                if(f(x)==f(y+p+q)||f(x+p+q)==f(y)){
                    cout<<"no\n";
                    tp=1;
                    break;
                }
                fa[f(x)]=f(y);
                fa[f(x+p+q)]=f(y+p+q);
            }
        }
        if(tp){
            continue;
        }
        for(int i=1;i<=p+q;i++){
            if(mp[f(i)]!=t){
                mp[f(i)]=t;
                v[++pt].clear();
                v[pt].push_back(i);
                mpp[pt]=f(i);
                mmp[f(i)]=pt;
                sz[pt]=1;
            }else{
                v[mmp[f(i)]].push_back(i);
                sz[mmp[f(i)]]++;
            }
        }
        for(int i=1;i<=pt;i++){
            for(int j=i;j<=pt;j++){
                if(f(mpp[i])!=f(mpp[j]-p-q)&&i!=j){
                    if(sz[i]+sz[j]==p){
                        ps++;
                        pi=i;
                        pj=j;
                    }
                }
            }
            if(sz[i]==p){
                ps++;
                pi=i;
                pj=0;
            }
        }
        if(ps!=1){
            cout<<"no\n";
            continue;       
        }
        for(int i=0;i<v[pi].size();i++){
            a[++aa]=v[pi][i];
        }
        for(int i=0;i<v[pj].size();i++){
            a[++aa]=v[pj][i];
        }
        sort(a+1,a+aa+1);
        for(int i=1;i<=aa;i++){
            cout<<a[i]<<"\n";
        }
        cout<<"end\n";
    }
    return 0;
}