大概做法
观察到答案贡献只有-1,0,1,2。
特判-1,0的情况。
如果存在割点,答案就为1
否则为2.
建图可以离散化,因为只有附近的8个格子才有可能成为割点。
详细做法
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<map>
#include<cstdlib>
#include<vector>
#define gc getchar()
#define ll long long
#define ull unsigned long long
#define file(s) freopen(s".in","r",stdin);freopen(s".out","w",stdout)
#define I inline
using namespace std;
const int N=25e5+5,M=1e6+5,mod=19260817;
const ull p0=31,p1=37;
template<class o>I void qr(o &x)
{
char c=gc;int f=1;x=0;
while(c<'0'||c>'9'){if(c=='-')f=-1;c=gc;}
while(c>='0'&&c<='9'){x=x*10+(c^48);c=gc;}
x*=f;
}
template<class o>I void qw(o x)
{
if(x<0)x=-x,putchar('-');
if(x/10)qw(x/10);
putchar(x%10+48);
}
void mn(int &x,int y){if(x>y)x=y;}
void mx(int &x,int y){if(x<y)x=y;}
int n,m,c;
struct Hash
{
struct edge{int x,y,next,op,dis;}a[N];int len,last[mod];
I void ins(int x,int y,int op,int dis)
{
if(x<=0||y<=0||x>=n+1||y>=m+1)return ;
int p=(1ll*(x-1)*m+y)%mod;
for(int k=last[p];k;k=a[k].next)
if(a[k].x==x&&a[k].y==y)
{
mn(a[k].dis,dis);
mx(a[k].op,op);
return ;
}
a[++len]=(edge){x,y,last[p],op,dis};last[p]=len;
}
I int qry(int x,int y)
{
if(x<=0||y<=0||x>=n+1||y>=m+1)return -1;
int p=(1ll*(x-1)*m+y)%mod;
if(!last[p])return -1;
for(int k=last[p];k;k=a[k].next)
if(a[k].x==x&&a[k].y==y)return k;
return -1;
}
I void clear()
{
for(int i=1;i<=len;i++)
{
int p=(1ll*(a[i].x-1)*m+a[i].y)%mod;
last[p]=0;a[i]=(edge){0,0,0,0,0};
}len=0;
}
}A;
int dx[N],dy[N];
bool ck()
{
if(1ll*n*m<=c+1)return 0;
if(1ll*n*m<=c+2)
{
int kx[3],ky[3];kx[0]=ky[0]=0;
for(int i=1;i<=c;i++)A.ins(dx[i],dy[i],1,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
if(A.qry(i,j)==-1)
kx[++kx[0]]=i,ky[++ky[0]]=j;
int d=abs(kx[1]-kx[2])+abs(ky[1]-ky[2]);
A.clear();
if(d==1)return 0;
}
return 1;
}
const int px[5]={0,-1,0,1,0};
const int py[5]={0,0,-1,0,1};
int f[N];bool vis[N];
int get(int x){return f[x]==x?x:f[x]=get(f[x]);}
void merge(int x,int y){f[get(y)]=get(x);}
void dfs(int x,int y,int anc)
{
int now=A.qry(x,y);
if(now==-1||vis[now]||A.a[now].op)return ;
vis[now]=1;merge(anc,now);
for(int i=1;i<=4;i++)dfs(x+px[i],y+py[i],anc);
}
void dfs(int x,int y,int col,int &flag)
{
int now=A.qry(x,y);
if(now==-1||vis[now]||flag)return ;
vis[now]=1;
for(int i=1;i<=4;i++)
{
int tx=x+px[i],ty=y+py[i],v=A.qry(tx,ty);
if(v!=-1&&!A.a[v].op)
{
if(!col)col=get(v);
else if(col!=get(v))
{
flag=1;
return ;
}
}
}
for(int i=1;i<=4;i++)
dfs(x+px[i],y+py[i],col,flag);
}
bool ck0()
{
for(int i=1;i<=A.len;i++)f[i]=i,vis[i]=0;
for(int i=1;i<=A.len;i++)
if(!A.a[i].op&&!vis[i])dfs(A.a[i].x,A.a[i].y,i);
for(int i=1;i<=A.len;i++)
if(A.a[i].op&&!vis[i])
{
int flag=0;dfs(A.a[i].x,A.a[i].y,0,flag);
if(flag)return 0;
}
return 1;
}
struct edge{int v,next;}a[N<<2];int len,last[N];
void ins(int u,int v){a[++len]=(edge){v,last[u]};last[u]=len;}
int dfn[N],low[N],cnt,cut,root;
void tarjan(int u)
{
if(cut)return ;
dfn[u]=low[u]=++cnt;int siz=0;
for(int k=last[u],v;k;k=a[k].next)
{
if(!dfn[v=a[k].v])
{
tarjan(v);
low[u]=min(low[u],low[v]);++siz;
if(dfn[u]<=low[v]&&A.a[u].dis==1)
{
if(u!=root||siz>1)
{
cut=1;
return ;
}
}
}
else low[u]=min(low[u],dfn[v]);
}
}
void work()
{
qr(n),qr(m),qr(c);
for(int i=1;i<=c;i++)qr(dx[i]),qr(dy[i]);
if(!ck()){puts("-1");return ;}
if(n==1)
{
sort(dy+1,dy+c+1);
int ans=1,p=1;
while(p<=c)
{
int loc=p;
while(loc<=c&&dy[loc+1]==dy[loc]+1)++loc;
if(dy[p]>1&&dy[p]<m)
{
ans=0;break;
}
p=loc+1;
}
qw(ans);puts("");
return ;
}
if(m==1)
{
sort(dx+1,dx+c+1);
int ans=1,p=1;
while(p<=c)
{
int loc=p;
while(loc<=c&&dx[loc+1]==dx[loc]+1)++loc;
if(dx[p]>1&&dx[p]<n)
{
ans=0;break;
}
p=loc+1;
}
qw(ans);puts("");
return ;
}
for(int i=1,x,y;i<=c;i++)
{
x=dx[i],y=dy[i];
for(int j=-2;j<=2;j++)
for(int k=-2;k<=2;k++)
{
int d=max(abs(j),abs(k));
if(!j&&!k)A.ins(x+j,y+k,1,d);
else A.ins(x+j,y+k,0,d);
}
}
for(int i=1,x,y;i<=A.len;i++)
{
if(A.a[i].op)continue;
x=A.a[i].x,y=A.a[i].y;
for(int l=1;l<=4;l++)
{
int tx=x+px[l],ty=y+py[l];
int v=A.qry(tx,ty);
if(~v&&!A.a[v].op)ins(i,v);
}
}
if(!ck0())
{
puts("0");
for(int i=1;i<=A.len;i++)last[i]=0;
cnt=0;
A.clear();return ;
}
cut=0;
for(int i=1;i<=A.len;i++)
if(!dfn[i])
{
root=i;tarjan(i);
if(cut)break;
}
cut?puts("1"):puts("2");
for(int i=1;i<=A.len;i++)
last[i]=dfn[i]=low[i]=0;
len=cnt=0;
A.clear();
}
int main()
{
file("grid17");
int T;qr(T);
while(T--)
{
work();
}
return 0;
}
最后一次更新于2020-05-25
0 条评论