题目大意

红包把它的南瓜灯划分成了$n\times m$的网格，并用 $(x,y)$表示第$x$行，第$y$列的格子

两个格子是相邻的当且仅当它们有一条公共边，特殊地，$(x,1)$和$(x,m)$，红包也视为是相邻的，但是他不把$(1,x)$和$(n,x)$当做是相邻的

然后删除$k$个网格，询问当前矩阵中是否满足任意两个网格之间有唯一路径

数据范围

戳我

题解

果然还是学艺不精，没看出来满足条件的矩阵都是树，然后全场跪系列

如果$n\times m$比$k$大很多的时候，则绝对不满足树的性质，即点数恰好比边数大1

我们根据这个性质，可以列出一个判定能否为树的不等式：$nm-k\geqslant 2nm-n-4k$，化简得到$3k+n\geqslant nm$

又因为我们已知$k$和$n$的范围，所以经过处理后可以得到：若数据为$nm>4\times 10^5$，直接输出No即可

此外，小数据用并查集判断是否是树，这很简单，也不详说了

程序

#include<cstdio>
#include<cmath>
#include<cstring>
#include<algorithm>
#define For(i,l,r) for(int i=l;i<=r;i++)
#define ll long long
using namespace std;
inline int read(){
    int x=0,f=1;char ch=getchar();
    while (ch<'0'||ch>'9') {if (ch=='-') f=-1;ch=getchar();}
    while (ch>='0'&&ch<='9') {x=x*10+ch-48;ch=getchar();}
    return x*f;
}

int t,n,m,k,flag,pos,root;
int f[300500],map[300500];
int getf(int x){return f[x]==x?x:f[x]=getf(f[x]);}
inline int spot(int x,int y){return (x-1)*m+y;}

int main(){
    t=read();
    while (t--){
        memset(map,1,sizeof(map));flag=1;
        n=read(),m=read(),k=read();
        if ((ll)n*m>300500){
            For(i,1,k) {int x=read(),y=read();}
            puts("No");continue;
        }
        For(i,1,k){
            int x=read(),y=read();
            map[spot(x,y)]=0;
        }
        For(i,1,n*m) f[i]=i;
        For(i,1,n){    
            For(j,1,m){
                if (!map[spot(i,j)]) continue;
                if (map[spot(i,j%m+1)]){
                    int fu=getf(spot(i,j)),fv=getf(spot(i,j%m+1));
                    if (fu==fv) flag=0;
                    else f[fu]=fv; 
                }
                if (!flag) break;
                if (i<n&&map[spot(i+1,j)]){
                    int fu=getf(spot(i,j)),fv=getf(spot(i+1,j));
                    if (fu==fv) flag=0;
                    else f[fu]=fv; 
                }
                if (!flag) break;
            }
            if (!flag) break;
        }
        if (flag){
            For(i,1,n*m) if (map[i]) {pos=i;root=getf(i);break;}
            For(i,pos+1,n*m) if (map[i]&&getf(i)!=root) {flag=0;break;}
        }
        if (flag) puts("Yes");
        else puts("No");
    }
    return 0;
}