3495: PA2010 Riddle 2-sat 前缀优化

链接

bzoj

思路

不想说啥了，看hwim的吧，我去睡觉了zZ。

代码

/**************************************************************

    Problem: 3495

    User: gryz2016

    Language: C++

    Result: Accepted

    Time:19152 ms

    Memory:178896 kb

****************************************************************/

#include <bits/stdc++.h>

using namespace std;

const int N=1e6+7;

int read() {

   int x=0,f=1;char s=getchar();

   for(;s>'9'||s<'0';s=getchar()) if(s=='-') f=-1;

   for(;s>='0'&&s<='9';s=getchar()) x=x*10+s-'0';

   return x*f;

}

int n,m,k;

struct node {

   int v,nxt;

}e[N*8];

int head[N*4],tot;

void add(int u,int v) {

   // cout<<u<<" "<<v<<"\n";

   e[++tot].v=v;

   e[tot].nxt=head[u];

   head[u]=tot;

}

int low[N*4],dfn[N*4],stak[N*4],top,vis[N*4],belong[N*4],scc,cnt;

void tarjan(int u) {

   low[u]=dfn[u]=++cnt;

   vis[u]=1;

   stak[++top]=u;

   for(int i=head[u];i;i=e[i].nxt) {

       int v=e[i].v;

       if(!dfn[v]) {

           tarjan(v);

           low[u]=min(low[u],low[v]);

       } else if(vis[v]) {

           low[u]=min(low[u],dfn[v]);

       }

   }

   if(low[u]==dfn[u]) {

       ++scc;

       while(stak[top]!=u) {

           belong[stak[top]]=scc;

           vis[stak[top]]=0;

           top--;

       }

       belong[stak[top]]=scc;

       vis[stak[top]]=0;

       top--;

   }

}

int main() {

   n=read(),m=read(),k=read();

   for(int i=1;i<=m;++i) {

       int x=read(),y=read();

       add(x+2*n,y),add(y+2*n,x);

   }

   for(int i=1;i<=n;++i) add(i,i+n),add(i+3*n,i+2*n); //a_i <-> S_i

   for(int i=1;i<=k;++i) {

       int num=read(),las=read();

       for(int j=2;j<=num;++j) {

           int x=read();

           add(x+3*n,las+3*n); //S_i <-> S_i-1

           add(las+n,x+n);

           add(x,las+3*n); //a_x <-> S_i-1

           add(las+n,x+2*n);

           las=x;

       }

   }

   for(int i=1;i<=4*n;++i)

        if(!dfn[i])

            tarjan(i);

   for(int i=1;i<=2*n;++i)

        if(belong[i]==belong[i+2*n]) return puts("NIE"),0;

   puts("TAK");

   return 0;

}