#include <bits/stdc++.h>
#define union khoaphamdangyeuhihixd
using namespace std;
int h1, w, p, q;
int last[2005][2005], dist[2005][2005];
queue<pair<int, int> > b;
string s[2005];
vector<pair<int, int> > adj[200005];
int dx[]={0, 1, 0, -1};
int dy[]={-1, 0, 1, 0};
vector<pair<int, pair<int, int> > > edges;
int f[200005], h[200005];
pair<int, int> anc[200005][20];
int find(int i)
{
return f[i]==i? f[i]:find(f[i]);
}
void union(int i, int j)
{
f[find(i)]=find(j);
}
bool check(int a, int b)
{
if(a>0&&b>0&&a<=h1&&b<=w&&s[a][b]!='#'&&!last[a][b])
{
return true;
}
return false;
}
void bfs()
{
while(b.size())
{
pair<int, int> fr=b.front();
b.pop();
for(int i=0; i<4; i++)
{
int ax=fr.first+dx[i], ay=fr.second+dy[i], ck=check(ax, ay);
if(ck)
{
last[ax][ay]=last[fr.first][fr.second];
dist[ax][ay]=dist[fr.first][fr.second]+1;
b.push({ax, ay});
}
else if(last[ax][ay]!=0)
{
edges.push_back({dist[ax][ay]+dist[fr.first][fr.second],{last[ax][ay], last[fr.first][fr.second]}});
}
}
}
}
void kruskal()
{
sort(edges.begin(), edges.end());
for(auto i:edges)
{
if(find(i.second.second)!=find(i.second.first))
{
union(i.second.first, i.second.second);
adj[i.second.first].push_back({i.second.second, i.first});
adj[i.second.second].push_back({i.second.first, i.first});
}
}
}
void dfs(int node, int fa)
{
h[node]=h[fa]+1;
anc[node][0].first=fa;
for(int i=1; i<=19; i++)
{
anc[node][i].first=anc[anc[node][i-1].first][i-1].first;
anc[node][i].second=max(anc[node][i-1].second, anc[anc[node][i-1].first][i-1].second);
}
for(auto i:adj[node])
{
if(i.first==fa)
{
continue;
}
anc[i.first][0].second=i.second;
dfs(i.first, node);
}
}
int lca(int u, int v)
{
// cout<<u<<" "<<v<<endl;
int lel=0;
if(h[u]<h[v])
{
swap(u, v);
}
for(int i=18; i>=0; i--)
{
if(h[anc[u][i].first]<h[v]) continue;
lel=max(lel, anc[u][i].second);
u=anc[u][i].first;
}
// cout<<u<<endl;
if(u==v) return lel;
for(int i=18; i>=0; i--)
{
if(anc[u][i].first==anc[v][i].first) continue;
lel=max(lel, max(anc[u][i].second, anc[v][i].second));
u=anc[u][i].first;
v=anc[v][i].first;
}
return max(lel, max(anc[u][0].second, anc[v][0].second));
}
signed main()
{
cin>>h1>>w>>p>>q;
for(int i=1; i<=p; i++)
{
f[i]=i;
}
for(int i=1; i<=h1; i++)
{
cin>>s[i];
s[i]='!'+s[i]+'!';
}
for(int i=1; i<=p; i++)
{
int u, v;
cin>>u>>v;
b.push({u, v});
last[u][v]=i;
}
bfs();
kruskal();
dfs(1, 1);
// for(int i=1; i<=h1; i++)
// {
// for(int j=1; j<=w; j++)
// {
// cout<<last[i][j]<<" ";
// }
// cout<<endl;
// }
for(int i=1; i<=q; i++)
{
int u, v;
cin>>u>>v;
cout<<lca(u, v)<<endl;
}
}
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
18 ms |
6204 KB |
Output is correct |
| 2 |
Incorrect |
21 ms |
7420 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Correct |
81 ms |
26484 KB |
Output is correct |
| 2 |
Correct |
175 ms |
16224 KB |
Output is correct |
| 3 |
Correct |
1006 ms |
94020 KB |
Output is correct |
| 4 |
Correct |
1989 ms |
143548 KB |
Output is correct |
| 5 |
Correct |
2456 ms |
143936 KB |
Output is correct |
| 6 |
Incorrect |
993 ms |
93964 KB |
Output isn't correct |
| 7 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
83 ms |
26480 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
Verdict |
Execution time |
Memory |
Grader output |
| 1 |
Incorrect |
1906 ms |
94128 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
