Submission #57567212

---

Source Code Expand

// LUOGU_RID: 176232591
#include<bits/stdc++.h>
using namespace std;
const int N=5e6+10;
int mx[4]={1,-1,0,0},my[4]={0,0,1,-1};
int h,w,q,ans;
pair<int,int>fa[5][N];
inline int calc(int x,int y)
{
	return x*(w+2)+y;
}
inline pair<int,int> find(int p,int x,int y)
{
	if(fa[p][calc(x,y)]==make_pair(x,y))
		return {x,y};
	return fa[p][calc(x,y)]=find(p,fa[p][calc(x,y)].first,fa[p][calc(x,y)].second);
}
inline void ch(int x,int y)
{
	if(x<=0||x>h||y<=0||y>w)
		return ;
	ans--;
	for(int i=0;i<4;i++)
		fa[i][calc(x,y)]={x+mx[i],y+my[i]};
	return ;
}
int main()
{
	ios::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin>>h>>w>>q;
	ans=h*w;
	for(int i=0;i<=h+1;i++)
		for(int j=0;j<=w+1;j++)
			for(int k=0;k<4;k++)
				fa[k][calc(i,j)]={i,j};
	for(int i=1,r,c;i<=q;i++)
	{
		cin>>r>>c;
		if(fa[1][calc(r,c)]==make_pair(r,c))
			ch(r,c);
		else
			for(int j=0;j<4;j++)
			{
				pair<int,int>g=find(j,r,c);
				ch(g.first,g.second);
			}
	}
	cout<<ans<<"\n";
	return 0;
}

Submission Info

Judge Result