P10665 [AMPPZ2013] Bytehattan

思路

由于本题强制在线，时光倒流无法进行。

换个角度思考，删边等于将格子合并。

n \times n

个格点形成的网格图中有

(n-1) \times (n-1)

个格子，以及一个代表网格图外部的虚拟格子。

考虑在什么情况下，边两端的格点会由连通变为不连通。

若在合并格子前，即将被合并的两个格子已经属于同一连通块，那么合并后必然会形成环，而这个环必然会将环内外的格点分开，使对应边两端的格点不连通；否则边两端的格点仍然连通。

并查集维护格子的连通情况即可。

时间复杂度为

\mathcal{O}(k \alpha(n^2))

，即

\mathcal{O}(n^2 \alpha(n^2))

。

Code

CPP

123456789101112131415161718192021222324252627282930313233343536373839404142434445464748495051525354555657585960616263646566#include<bits/stdc++.h>
#define int long long

const int N=1510;

using namespace std;

int n,q,lst=1,fa[N*N],siz[N*N],id[N][N];

int x,y;

char op;

inline int read(){
	int ret=0,f=1;char ch=getchar();
	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
	while(ch>='0'&&ch<='9')ret=ret*10+(ch&15),ch=getchar();
	return ret*f;
}

inline char read1(){
	char ch=getchar();
	while(ch!='N'&&ch!='E')ch=getchar();
	return ch;
}

void _init(){
	for(int i=1;i^n;i++)for(int j=1;j^n;j++)id[i][j]=(i-1)*n+j;
	for(int i=1;i^n;i++)for(int j=1;j^n;j++)fa[id[i][j]]=id[i][j],siz[id[i][j]]=1;
}

int getfa(int x){
	return (fa[x]==x)?x:(fa[x]=getfa(fa[x]));
}

void _uni(int x,int y){
	if(siz[x]>siz[y])swap(x,y);
	fa[x]=y;
	siz[y]+=siz[x];
}

void add(int x,int y,int _x,int _y){
	int u=id[x][y],v=id[_x][_y];
	int fx=getfa(u),fy=getfa(v);
	if(fx^fy)lst=1,_uni(fx,fy);
	else lst=0;
}

signed main(){
	n=read(),q=read();
	_init();
	while(q--){
		if(lst){
			x=read(),y=read(),op=read1();
			read(),read(),read1();
		}else{
			read(),read(),read1();
			x=read(),y=read(),op=read1();
		}
		if(op=='N')add(x,y,x-1,y);
		else add(x,y,x,y-1);
		if(lst)printf("TAK\n");
		else printf("NIE\n");
	}
	return 0;
}

P10665 [AMPPZ2013] Bytehattan

文章操作

思路

Code

相关推荐

评论

P10665 [AMPPZ2013] Bytehattan