3495: PA2010 Riddle 2-sat 前缀优化
2024-08-28 10:30:34
3495: PA2010 Riddle 2-sat 前缀优化
链接
思路
不想说啥了,看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;
}
最新文章
- ionic常用的命令
- 0525 Scrum 项目 7.0
- OpenStreetMap/Google/百度/Bing瓦片地图服务(TMS)
- 在VS中向命令行添加参数的方法
- [IIS]IIS扫盲(六)
- 好文EF
- CentOS 安装 mono
- P1026 犁田机器人
- url传递中文的解决方案
- C#程序中将图片转换为二进制字符串,并将二进制字符串转换为图片
- UIView 弹出动画
- SymPy-符号运算好帮手
- 为Linux用ISO制作U盘启动及基本原理
- 一C++PSO(PSO)算法
- 关于H5从PC端切换到移动端,屏幕显示内容由横向转为竖向的研究!
- ";unexpected console statement” in Node.js
- EF Code First列名 &#39;Discriminator&#39; 无效的问题
- 2019 年起如何开始学习 ABP 框架系列文章-开篇有益
- [ICLR&#39;17] DEEPCODER: LEARNING TO WRITE PROGRAMS
- my phone blackberry classic / passport / priv / keyone