# Atcoder 3916 simple apsp problem

## 搜索神仙题

Posted by yjjr's blog on April 3, 2018

# code

#include<iostream>
#include<cstdio>
#include<cstdlib>
#include<cmath>
#include<cstring>
#include<algorithm>
#include<vector>
#define rep(i,a,b) for(register int i=a;i<=b;i++)
#define dep(i,a,b) for(register int i=a;i>=b;i--)
#define ll long long
#define mem(x,num) memset(x,num,sizeof x)
#define reg(x) for(int i=last[x];i;i=e[i].next)
using namespace std;
ll f=1,x=0;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
#define pb push_back
#define inf 1e9
const int maxn=66,maxm=1e6+6,dx[4]={-1,1,0,0},dy[4]={0,0,-1,1},mod=1e9+7;
struct node{int x,y;}a[maxn<<1],que[maxn*maxn*4];
bool fb[maxn][maxn],mark1[maxm],mark2[maxm];
vector<int>px,py;
void vnique(vector <int> &r){
sort(r.begin(),r.end());
auto t=unique(r.begin(),r.end());
r.erase(t,r.end());
}
void bfs(int x,int y){
rep(i,0,lx)rep(j,0,ly)dis[i][j]=inf;
rep(i,0,3){
int nex=nx+dx[i],ney=ny+dy[i];
if(nex>lx||nex<0||ney>ly||ney<0||dis[nex][ney]<=dis[nx][ny]+1||fb[nex][ney])continue;
dis[nex][ney]=dis[nx][ny]+1;que[++tail]=(node){nex,ney};
}
}
}
int main()
{
px.pb(1);px.pb(n+1);py.pb(1);py.pb(m+1);
rep(i,1,n)s1[i]=m;
rep(i,1,m)s2[i]=n;
rep(i,1,K){
px.pb(a[i].x),px.pb(a[i].x+1);
py.pb(a[i].y),py.pb(a[i].y+1);
s1[a[i].x]--,mark1[a[i].x]=1;
s2[a[i].y]--,mark2[a[i].y]=1;
}
rep(i,1,n)s1[i]=(s1[i]+s1[i-1])%mod;
rep(i,1,m)s2[i]=(s2[i]+s2[i-1])%mod;
rep(i,1,n-1)if(!mark1[i]&&!mark1[i+1])ans=(ans+1ll*2*s1[i]*(s1[n]-s1[i]))%mod;
rep(i,1,m-1)if(!mark2[i]&&!mark2[i+1])ans=(ans+1ll*2*s2[i]*(s2[m]-s2[i]))%mod;
vnique(px);vnique(py);lx=px.size()-2;ly=py.size()-2;
rep(i,1,K)
fb[lower_bound(px.begin(),px.end(),a[i].x)-px.begin()][lower_bound(py.begin(),py.end(),a[i].y)-py.begin()]=1;
rep(i,0,lx)rep(j,0,ly)cnt[i][j]=1ll*(px[i+1]-px[i])*(py[j+1]-py[j])%mod;
rep(i,0,lx)rep(j,0,ly)
if(!fb[i][j]){
bfs(i,j);
rep(k,0,lx)rep(p,0,ly)
if(!fb[k][p])ans=(ans+1ll*cnt[i][j]*dis[k][p]%mod*cnt[k][p])%mod;
}
ans=(ans+mod)%mod;ans=1ll*ans*(mod/2+1)%mod;
cout<<ans<<endl;
return 0;
}