Submission #67336468

---

Source Code Expand

//# pragma GCC target("avx2")
# pragma GCC optimize("O3")
# pragma GCC optimize("unroll-loops")
#include <bits/stdc++.h>
#define rep(i,n) for(int i=0;i<(n);i++)
#include"atcoder/all"
using namespace atcoder;
typedef modint998244353 mi;
using namespace std;
#define all(a) a.begin(),a.end()
#define compress(a) sort(all(a));a.erase(unique(all(a)),a.end())
typedef long long ll;
typedef pair<ll,ll> P;
constexpr ll mod=998244353;
constexpr ll inf=3e18;

int dx[]={1,0,-1,0},dy[]={0,1,0,-1};

int main(){
	int h,w,k;
	cin>>h>>w>>k;
	vector<vector<ll>>dp(h,vector<ll>(w,1e9));
	vector<vector<vector<int>>> nbh(h,vector<vector<int>>(w));
	rep(i,k){
		int r,c;
		cin>>r>>c;
		dp[r-1][c-1]=0;
	}
	queue<P>Q;
	rep(i,h){
		rep(j,w){
			if(dp[i][j]!=1e9){
				rep(k,4){
					if(0<=i+dx[k]&&i+dx[k]<h&&0<=j+dy[k]&&j+dy[k]<w){
						nbh[i+dx[k]][j+dy[k]].push_back(dp[i][j]);
					}
				}
			}
		}
	}
	rep(i,h){
		rep(j,w){
			if(nbh[i][j].size()>=2&&dp[i][j]>=1e9){
				sort(all(nbh[i][j]));
				Q.push({i,j});
			}
		}
	}

	while(Q.size()){
		P p=Q.front();
		Q.pop();
		//cout<<p.first<<" "<<p.second<<endl;
		//getchar();
		if(dp[p.first][p.second]<1e9)continue;
		sort(all(nbh[p.first][p.second]));
		dp[p.first][p.second]=nbh[p.first][p.second][1]+1;
		rep(k,4){
			int ni=p.first+dx[k],nj=p.second+dy[k];
			if(0<=ni&&ni<h&&0<=nj&&nj<w&&dp[ni][nj]>=1e9){
				nbh[ni][nj].push_back(dp[p.first][p.second]);
				if(nbh[ni][nj].size()>=2)Q.push({ni,nj});
			}
		}
	}

	ll ans=0;
	rep(i,h)rep(j,w)if(dp[i][j]<1e9)ans+=dp[i][j];
	cout<<ans<<endl;
}

Submission Info

Judge Result