Description
Sample Input
Input1:
3 2
1 0 2 1
1 0 2 0
1 1 2 1
Input2:
2 1
1 0 1 0
1 1 1 1
Sample Output
Output1:
0
1
Output2:
IMPOSSIBLE
Data Constraint
题解
此题稍微运用到一点点的2-SAT知识。
前置芝士：2-SAT
康这里！
现在我们知道了2-SAT，那看看这题怎么用。
分析原题题意：有很多个水阀，然后水阀有两个阀门，只有关掉一个阀门，水阀就会关闭。然后这两个阀门又分别对应着一个开关，开关的方式和上面的一样。
考虑2-SAT模型！
先把每个开关拆成两个点，一个表示开启，一个表示关闭。
然后再看到阀门，我们发现，任意两个阀门必须要有一个开启，所以我们可以连边。
连完边之后就会出现环的情况，于是我们就可以用tarjan把这个环缩掉。
当然，这时候还需要判断是不是某个开关的两个点都在同一个环中，如果是就无解。
缩完点后就变成了一个dag。建立反向边，直接跑一边拓补序即可。
当然，还要判断开关两个点在不同链的情况，要舍掉其中一个。
代码
#include<cstdio>
#include<cstring>
#define min(a,b) ((a)<(b)?(a):(b))using namespace std;int n,m,q,g;
int final[2000001],b[1000001],nex[1000001];
int fir[2000001],c[1000001],las[1000001];
int dfn[2000001],low[1000001],st[1000001],bz[1000001];
int l[1000001],r[1000001],a[1000001],f[1000001];
int ans[1000001],deg[1000001],d[1000001];void link(int x,int y)
{b[++q]=y;nex[q]=final[x];final[x]=q;
}void dg(int x)
{dfn[x]=low[x]=++g;st[++st[0]]=x;bz[x]=1;for(int j=final[x];j;j=nex[j])if(!dfn[b[j]]){dg(b[j]);low[x]=min(low[x],low[b[j]]);}else if(bz[b[j]])low[x]=min(low[x],dfn[b[j]]);if(low[x]==dfn[x]){l[x]=q+1;for(;st[st[0]]!=x;st[0]--){int u=st[st[0]];bz[u]=0,a[++q]=u,f[u]=x;}bz[x]=0,a[++q]=x,f[x]=x;st[0]--;r[x]=q;}
}int pd(int x)
{for(int i=l[x];i<=r[x];i++)if(ans[(a[i]-1)%m+1]>=0)return 1;return 0;
}void get(int x)
{for(int i=l[x];i<=r[x];i++)ans[(a[i]-1)%m+1]=(a[i]-1)/m;
}void solve()
{int t=1,w=0;for(int i=1;i<=2*m;i++)if((f[i]==i)&&(!deg[i]))d[++w]=i;for(;t<=w;t++){int x=d[t];if(pd(x))continue;get(x);for(int j=fir[x];j;j=las[j]){deg[c[j]]--;if(!deg[c[j]])d[++w]=c[j];}}
}int main()
{scanf("%d%d",&n,&m);memset(final,0,sizeof(final));for(int i=1;i<=n;i++){int u,v,x,y;scanf("%d%d%d%d",&u,&x,&v,&y);link(u+(x^1)*m,v+y*m);link(v+(y^1)*m,u+x*m);}memset(dfn,0,sizeof(dfn));memset(bz,0,sizeof(bz));st[0]=0;g=0;q=0;for(int i=1;i<=2*m;i++)if(!dfn[i])dg(i);for(int i=1;i<=m;i++)if(f[i]==f[i+m]){printf("IMPOSSIBLE\n");return 0;}memset(fir,0,sizeof(fir));memset(deg,0,sizeof(deg));q=0;for(int i=1;i<=2*m;i++)for(int j=final[i];j;j=nex[j])if(f[i]!=f[b[j]]){c[++q]=f[i];las[q]=fir[f[b[j]]];fir[f[b[j]]]=q;deg[f[i]]++;}memset(ans,128,sizeof(ans));solve();for(int i=1;i<=m;i++)printf("%d\n",ans[i]);
}