做pc端网站适配,河北seo技术,美丽乡村建设网站,网站邮件模板解析
看起来很不码农但写起来其实还行的一道题。 主要也是因为我贺题解把所有的雷都避过去了
首先一个比较显然的结论是#xff1a;通过堵角上的#xff0c;答案不超过2。 所以本题只要把答案是-1#xff0c;0#xff0c;1#xff0c;2的情况判出来即可。
-1是只有一个…解析
看起来很不码农但写起来其实还行的一道题。 主要也是因为我贺题解把所有的雷都避过去了
首先一个比较显然的结论是通过堵角上的答案不超过2。 所以本题只要把答案是-1012的情况判出来即可。
-1是只有一个空位或只有两个相邻空位。 0是原图不连通。 1是原图存在割点。 其他都是2。
做完了太天真了。
n,m≤109n,m\le 10^9n,m≤109
那咋办 注意到c≤105c\le 10^5c≤105这张图非常稀疏在空网格上暴力tarjan看起来非常的蠢。 那怎么办 我们尝试对于每个蛐蛐提取出它周围的格子这样的节点数就变成了 O(c)O(c)O(c) 级别。感觉有些像华容道那个题 然后在新的图上tarjan就好了。
还要注意亿点点坑点
提出的“周围一圈”应该是 5×55\times 55×5 而不是 3×33\times 33×3同时只有距离最近蛐蛐曼哈顿距离为1的点是割点才算割点。判联通的时候要把8联通的蛐蛐全找出来一起判。
代码
#includebits/stdc.h
using namespace std;
#define ll long long
#define ull unsigned long long
#define debug(...) fprintf(stderr,__VA_ARGS__)
#define ok debug(OK\n)
using namespace std;const int N1e5100;const int mod1333331;
const double inf1e9;
inline ll read(){ll x(0),f(1);char cgetchar();while(!isdigit(c)) {if(c-)f-1;cgetchar();}while(isdigit(c)) {x(x1)(x3)c-0;cgetchar();}return x*f;
}int n,m,c;
bool flag0;struct node{int to,nxt;
}p[N*25*4*2];
int fi[N*25],cnt;
inline void addline(int x,int y){p[cnt](node){y,fi[x]};fi[x]cnt;
}struct Hash{node p[N*25];int fi[mod1],tot,cnt;ll key[N*25];int id[N*25];void ins(int x,int y,int Id){ll w1ll*x*(m1)y,ow%mod;tot;id[tot]Id;key[tot]w; p[cnt](node){tot,fi[o]};fi[o]cnt;//debug(add o%lld fi%d\n,o,fi[o]);}int find(int x,int y){ll w1ll*x*(m1)y,ow%mod;for(int ifi[o];~i;ip[i].nxt){//debug(o%lld i%d\n,o,i);//ok;if(key[p[i].to]w) return id[p[i].to];}return 0;}void init(){tot0;memset(fi,-1,sizeof(fi));cnt-1;}
}mp;int tot;int x[N],y[N];
bool jd[N*25];
int d24x[25]{0,-2,-2,-2,-2,-2,-1,-1,-1,-1,-1,0,0,0,0,1,1,1,1,1,2,2,2,2,2},d24y[25]{0,-2,-1,0,1,2,-2,-1,0,1,2,-2,-1,1,2,-2,-1,0,1,2,-2,-1,0,1,2};
int d8x[9]{0,-1,-1,-1,0,0,1,1,1},d8y[9]{0,-1,0,1,-1,1,-1,0,1};
int d4x[5]{0,-1,0,0,1},d4y[5]{0,0,-1,1,0};int cut;
int dfn[N*25],low[N*25],tim,bel[N*25],Id;
void tarjan(int x,int rt0){dfn[x]low[x]tim;bel[x]Id;int son(0);for(int ifi[x];~i;ip[i].nxt){int top[i].to;//if(toc) continue;if(!dfn[to]){tarjan(to);son;if(low[to]dfn[x]){cutjd[x];}low[x]min(low[x],low[to]);}else low[x]min(low[x],dfn[to]);}if(rtson1) cut-jd[x];return;
}bool vis[N];
int nowId;
void dfs(int x,int y){int nowmp.find(x,y);vis[now]1;for(int d1;d8;d){int nxxd8x[d],nyyd8y[d];if(nx1||nxn||ny1||nym) continue;int tomp.find(nx,ny);if(toc){if(nowId0) nowIdbel[to];else if(nowId!bel[to]) nowId-1;}else if(!vis[to]) dfs(nx,ny); }
}void clear(){mp.init();memset(fi,-1,sizeof(int)*(tot1));cnt-1;memset(jd,0,sizeof(int)*(tot1));cuttimId0;memset(dfn,0,sizeof(int)*(tot1));memset(low,0,sizeof(int)*(tot1));memset(bel,0,sizeof(int)*(tot1));memset(vis,0,sizeof(int)*(c1));tot0;
}void work(){nread();mread();totcread();for(int i1;ic;i){x[i]read();y[i]read();mp.ins(x[i],y[i],i); }for(int i1;ic;i){for(int d1;d24;d){int nxx[i]d24x[d],nyy[i]d24y[d];if(nx1||nxn||ny1||nym) continue; if(!mp.find(nx,ny)){mp.ins(nx,ny,tot);int xtot;for(int d1;d4;d){int nnxnxd4x[d],nnynyd4y[d];int tomp.find(nnx,nny);if(totoc){//printf(d%d (%d %d) - (%d %d)\n,d,nx,ny,nnx,nny);addline(x,to);addline(to,x);}}}int tomp.find(nx,ny);if(toc) continue;if(abs(nx-x[i])1abs(ny-y[i])1) jd[to]1;}}if(flag) for(int i1;in;i){for(int j1;jm;j) printf(%d ,mp.find(i,j));puts();}for(int ic1;itot;i){if(!dfn[i]){Id;tarjan(i,1);}}if(1ll*n*m-c2||(1ll*n*m-c2(Id1||n*m2))){puts(-1);return;}for(int i1;ic;i){if(!vis[i]){nowId0;dfs(x[i],y[i]);if(nowId-1){puts(0);return;}}}if(cut||n1||m1) puts(1);else puts(2);return;
}signed main(){#ifndef ONLINE_JUDGEfreopen(a.in,r,stdin);freopen(a.out,w,stdout);#endifmemset(fi,-1,sizeof(fi));cnt-1;int Tread();while(T--){clear();work();}return 0;
}
