#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
const int P = 2e5 + 5;
const int Tx[] = {-1, 0, 1, 0};
const int Ty[] = {0, 1, 0, -1};
typedef pair <int,int> pi;
char a[N][N];
int dist[N][N], id[N][N];
queue <pi> q;
vector <pair <int, pi> > edge;
int dep[P], up[P][25], anc[P][25];
int link[P], size[N];
vector <pi> g[P];
int H, W, p, que;
bool vis[P];
void dfs(int u, int p)
{
vis[u] = 1;
for(int i = 1; i <= 20; i++)
{
anc[u][i] = anc[anc[u][i - 1]][i - 1];
up[u][i] = max(up[u][i - 1], up[anc[u][i - 1]][i - 1]);
}
for(auto x : g[u])
{
int v = x.first, w = x.second;
if(v == p)
continue;
dep[v] = dep[u] + 1,
anc[v][0] = u, up[v][0] = w;
dfs(v, u);
}
}
void init()
{ for(int i=1;i<=p;i++) link[i] = i; for(int i=1;i<=p;i++) size[i] = 1; }
int find(int x)
{ while(x != link[x]) x = link[x]; return x; }
bool same(int a,int b)
{ return find(a) == find(b); }
void unite(int a,int b)
{ a = find(a); b = find(b); if(size[a] < size[b]) swap(a,b); size[a] += size[b]; link[b] = a; }
bool ck(int x, int y)
{ return (x >= 1 && y >= 1 && x <= H && y <= W && a[x][y] == '.'); }
int max_path(int u, int v)
{
if (!same(u, v)) return -1;
int ans = 0;
if (dep[u] < dep[v]) swap(u, v);
for (int i = 20; i >= 0; --i) if (dep[u] - (1 << i) >= dep[v]) ans = max(ans, up[u][i]), u = anc[u][i];
if (u == v) return ans;
for (int i = 20; i >= 0; --i) if (anc[u][i] != anc[v][i]) ans = max(ans, max(up[u][i], up[v][i])), u = anc[u][i], v = anc[v][i];
return max(ans, max(up[u][0], up[v][0]));
}
void bfs()
{
while(q.size() > 0)
{
int x = q.front().first,
y = q.front().second;
// cout << x << ' ' << y << '\n';
q.pop();
for(int i = 0; i < 4; i++)
{
int nx = x + Tx[i], ny = y + Ty[i];
if(ck(nx, ny) == 1 && dist[nx][ny] == -1)
{
dist[nx][ny] = dist[x][y] + 1,
id[nx][ny] = id[x][y];
q.push({nx, ny});
}
if(ck(nx, ny) && dist[nx][ny] != -1)
{
int a = id[nx][ny], b = id[x][y];
if(a != b)
{
// cout << a << ' ' << b << endl;
edge.push_back({dist[nx][ny] + dist[x][y], {a, b}});
}
}
}
}
}
int main()
{
ios_base::sync_with_stdio(false);
cin.tie(0);
cin >> H >> W >> p >> que;
init();
for(int i = 1; i <= H; i++)
{
for(int j = 1; j <= W; j++)
{
dist[i][j] = -1;
id[i][j] = 0;
cin >> a[i][j];
}
}
for(int i = 1; i <= p; i++)
{
int x, y; cin >> x >> y;
// cout << x << y << endl;
dist[x][y] = 0;
id[x][y] = i;
q.push({x, y});
}
bfs();
sort(edge.begin(), edge.begin());
for(auto e : edge)
{
int x = e.second.first,
y = e.second.second;
if(!same(x, y))
{
// cout << x << ' ' << y << '\n';
g[x].push_back({y, e.first});
g[y].push_back({x, e.first});
unite(x, y);
}
}
for(int i = 1; i <= p; i++)
{
if(vis[i] == 0)
dfs(i, i);
}
while(que--)
{
int s, t;
cin >> s >> t;
cout << max_path(s, t) << '\n';
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
9 ms |
5880 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Correct |
40 ms |
27268 KB |
Output is correct |
| 2 |
Incorrect |
55 ms |
10920 KB |
Output isn't correct |
| 3 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
45 ms |
27204 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Incorrect |
497 ms |
44116 KB |
Output isn't correct |
| 2 |
Halted |
0 ms |
0 KB |
- |
