MnZn求助2-sat
查看原帖
MnZn求助2-sat
420129
Nt_Tsumiki楼主2023/9/30 08:35

#7WA

#include <iostream>
#include <cstdio>
#include <string>

using namespace std;
int n,cnt,dfncnt,sccnum,top,tcnt,pcnt=1,b;
string str[500001];
int s[5000001],head[5000001],dfn[5000001],low[5000001],scc[5000001],p[500001][2],v[2000001][3];

struct Node { int to,nxt; }e[20000001];
struct Tree { int ch[2],id; }t[2000001];

void add(int x,int y) { e[++cnt]=Node{y,head[x]},head[x]=cnt; }

void tarjan(int x) {
    dfn[x]=low[x]=++dfncnt,s[++top]=x;
    for (int i=head[x];i;i=e[i].nxt) {
        int y=e[i].to;
        if (!dfn[y]) {
            tarjan(y);
            low[x]=min(low[x],low[y]);
        } else if (!scc[y]) low[x]=min(low[x],dfn[y]);
    }
    if (dfn[x]==low[x]) {
        ++sccnum;
        do scc[s[top]]=sccnum; while (s[top--]!=x);
    }
}

void ins(int x,string s,int k,int id,int fa) {
    if (k==s.size()) {
        ++v[x][0];
        if (v[x][0]>2) {
            b=1;
            return;
        }
        v[x][v[x][0]]=id;
        if (fa!=-1) add(t[fa].id,id),add(id^1,t[fa].id^1);
        add(id^1,t[x].id),add(t[x].id^1,id);
        return;
    }
    if (s[k]!='?') {
        if (!t[x].ch[s[k]-'0']) {
            t[x].ch[s[k]-'0']=++tcnt,t[t[x].ch[s[k]-'0']].id=(pcnt+=2);
            add(t[x].id,t[t[x].ch[s[k]-'0']].id),add(t[t[x].ch[s[k]-'0']].id^1,t[x].id^1);
        }
        ins(t[x].ch[s[k]-'0'],s,k+1,id,x);
    } else {
        if (!t[x].ch[0]) {
            t[x].ch[0]=++tcnt,t[t[x].ch[0]].id=(pcnt+=2);
            add(t[x].id,t[t[x].ch[0]].id),add(t[t[x].ch[0]].id^1,t[x].id^1);
        }
        ins(t[x].ch[0],s,k+1,id^1,x);
        if (!t[x].ch[1]) {
            t[x].ch[1]=++tcnt,t[t[x].ch[1]].id=(pcnt+=2);
            add(t[x].id,t[t[x].ch[1]].id),add(t[t[x].ch[1]].id^1,t[x].id^1);
        }
        ins(t[x].ch[1],s,k+1,id,x);
    }
}

int main() {
    scanf("%d",&n);
    for (int i=1;i<=n;i++) {
        cin>>str[i];
        p[i][0]=++pcnt,p[i][1]=++pcnt;
    }
    t[0].id=(pcnt+=2);
    for (int i=1;i<=n;i++) {
        ins(0,str[i],0,p[i][0],-1);
        if (b) return !printf("NO\n");
    }
    for (int i=1;i<=tcnt;i++)
        for (int j=1;j<=v[i][0];j++)
            for (int k=1;k<=v[i][0];k++)
                if (j!=k) add(v[i][j]^1,v[i][k]),add(v[i][j],v[i][k]^1);
    for (int i=1;i<=pcnt;i++)
        if (!dfn[i]) tarjan(i);
    for (int i=1;i<=n;i++)
        if (scc[p[i][0]]==scc[p[i][1]]) return !printf("NO\n");
    printf("YES\n");
    for (int i=1;i<=n;i++) 
        if (scc[p[i][0]]<scc[p[i][1]]) {
            for (auto &j:str[i]) 
                if (j=='?') {
                    j='0';
                    break;
                }
        } else {
            for (auto &j:str[i]) 
                if (j=='?') {
                    j='1';
                    break;
                }
        }
    for (int i=1;i<=n;i++) cout<<str[i]<<endl;
    return 0;
}
2023/9/30 08:35
加载中...