WA on test #13(2sat)
查看原帖
WA on test #13(2sat)
399475
_XHY20180718_楼主2023/7/14 17:14

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;
}
2023/7/14 17:14
加载中...