RT, 2-SAT算法,WA on test #13
错误信息:
The 1-th set don't contain a-14005
不知道是什么问题 awa 。
#include<bits/stdc++.h>
using namespace std;
const int N=3e5+9;
int n,a,b,p[N],c[N];
int ltk[N],id;
int dfn[N],low[N],Time;
int head[N],ei;
bool vis[N];
map<int,int>mp;
stack<int>st;
struct edge{
int v,nxt;
}egs[N<<1];
inline void add(int u,int v)
{
egs[++ei].v=v;
egs[ei].nxt=head[u];
head[u]=ei;
}
inline void tarjan(int u)
{
st.push(u),vis[u]=1;
dfn[u]=low[u]=++Time;
for(int i=head[u]; i; i=egs[i].nxt)
{
int v=egs[i].v;
if(!dfn[v])tarjan(v),low[u]=min(low[u],low[v]);
else if(vis[v])low[u]=min(low[u],dfn[u]);
}
if(dfn[u]==low[u])
{
int v;++id;
do{
v=st.top(),st.pop();
vis[v]=0,ltk[v]=id;
}while(u!=v);
}
}
signed main()
{
cin>>n>>a>>b;
for(int i=1; i<=n; ++i)
cin>>p[i],mp[p[i]]=i;
int u,v;
for(int i=1; i<=n; ++i)
{
u=v=0;
if(mp.count(a-p[i]))u=mp[a-p[i]];
if(mp.count(b-p[i]))v=mp[b-p[i]];
if(u&&v)add(i,u),add(i,v),add(i+n,v+n),add(i+n,u+n);
else if(u)add(u+n,u),add(i+n,i);
else if(v)add(v,v+n),add(i,i+n);
else{cout<<"NO\n";return 0;}
}
for(int i=1; i<=(n<<1); ++i)
if(!dfn[i])Time=0,tarjan(i);
for(int i=1; i<=n; i++)
if(ltk[i]==ltk[i+n]){cout<<"NO\n";return 0;}
cout<<"YES\n";
for(int i=1; i<=n; i++)
cout<<(ltk[i]>ltk[i+n])<<' ';
return 0;
}