This submission is migrated from previous version of oj.uz, which used different machine for grading. This submission may have different result if resubmitted.
#include <bits/stdc++.h>
using namespace std;
typedef pair<int,int> ii;
typedef pair<int,ii> iii;
int X[]={0,0,-1,1};
int Y[]={-1,1,0,0};
int m,n,k,T,R[200005],h[200005],Com[200005],P[200005][20],maxd[200005][20],d[2005][2005],Pre[2005][2005];
ii Imp[200005];
char a[2005][2005];
vector<ii> g[200005];
vector<iii> Edge;
queue<ii> Q;
int Find(int u)
{
if(u==R[u])
return u;
return R[u]=Find(R[u]);
}
void Union(int u,int v)
{
if(u>v)
R[u]=v;
else
R[v]=u;
}
void InitTree()
{
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
d[i][j]=-1;
for(int i=1;i<=k;i++)
{
Pre[Imp[i].first][Imp[i].second]=i;
d[Imp[i].first][Imp[i].second]=0;
Q.push(Imp[i]);
}
while(Q.size()>0)
{
int u=Q.front().first;
int v=Q.front().second;
Q.pop();
for(int i=0;i<=3;i++)
{
int uu=u+X[i];
int vv=v+Y[i];
if(uu>0&&uu<=m&&vv>0&&vv<=n&&a[uu][vv]!='#')
{
if(d[uu][vv]==-1)
{
Q.push(ii(uu,vv));
d[uu][vv]=d[u][v]+1;
Pre[uu][vv]=Pre[u][v];
}
else
if(Pre[uu][vv]!=Pre[u][v])
Edge.push_back(iii(d[u][v]+d[uu][vv],ii(Pre[u][v],Pre[uu][vv])));
}
}
}
for(int i=1;i<=k;i++)
R[i]=i;
sort(Edge.begin(),Edge.end());
for(int i=0;i<Edge.size();i++)
{
int u=Find(Edge[i].second.first);
int v=Find(Edge[i].second.second);
if(u!=v)
{
g[Edge[i].second.first].push_back(ii(Edge[i].second.second,Edge[i].first));
g[Edge[i].second.second].push_back(ii(Edge[i].second.first,Edge[i].first));
Union(u,v);
}
}
}
void DFS(int u,int high,int kk)
{
Com[u]=kk;
h[u]=high;
for(int i=0;i<g[u].size();i++)
if(h[g[u][i].first]==0)
{
P[g[u][i].first][0]=u;
maxd[g[u][i].first][0]=g[u][i].second;
DFS(g[u][i].first,high+1,kk);
}
}
int LCA(int u,int v)
{
int rs=0;
for(int k=18;k>=0;k--)
if(h[P[u][k]]>=h[v])
{
rs=max(rs,maxd[u][k]);
u=P[u][k];
}
else
if(h[P[v][k]]>=h[u])
{
rs=max(rs,maxd[v][k]);
v=P[v][k];
}
for(int k=18;k>=0;k--)
if(P[u][k]!=P[v][k])
{
rs=max(rs,maxd[u][k]);
rs=max(rs,maxd[v][k]);
u=P[u][k];
v=P[v][k];
}
while(u!=v)
{
rs=max(rs,maxd[u][0]);
rs=max(rs,maxd[v][0]);
u=P[u][0];
v=P[v][0];
}
return rs;
}
int main()
{
ios_base::sync_with_stdio(false);
//freopen("TEST.INP","r",stdin);
cin>>m>>n>>k>>T;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
cin>>a[i][j];
for(int i=1;i<=k;i++)
cin>>Imp[i].first>>Imp[i].second;
InitTree();
int Count=0;
for(int i=1;i<=k;i++)
if(h[i]==0)
DFS(i,1,++Count);
for(int k=1;k<=18;k++)
for(int i=1;i<=n;i++)
{
P[i][k]=P[P[i][k-1]][k-1];
maxd[i][k]=max(maxd[i][k-1],maxd[P[i][k-1]][k-1]);
}
int u,v;
while(T--)
{
cin>>u>>v;
if(Com[u]!=Com[v])
cout<<-1<<"\n";
else
cout<<LCA(u,v)<<"\n";
}
}
Compilation message (stderr)
bottle.cpp: In function 'void InitTree()':
bottle.cpp:67:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<Edge.size();i++)
^
bottle.cpp: In function 'void DFS(int, int, int)':
bottle.cpp:84:18: warning: comparison between signed and unsigned integer expressions [-Wsign-compare]
for(int i=0;i<g[u].size();i++)
^
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |
# | Verdict | Execution time | Memory | Grader output |
---|
Fetching results... |