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;
}