#include <cstdio>
#include <queue>
#include <vector>
#include <algorithm>
#include <utility>
using namespace std;
typedef pair<int,int> pi;
struct edg{int s,e,x;};
vector<edg> tree;
vector<pi> graph[200005];
bool cmp(edg a, edg b){return a.x < b.x;}
int n,m,p,q;
char str[2005][2005];
int reg[2005][2005], dist[2005][2005];
int pa[200005][18], val[200005][18], dep[200005];
struct disj{
int pa[200005];
void init(int n){
for(int i=0; i<=n; i++) pa[i] = i;
}
int find(int x){
if(pa[x] == x) return x;
return pa[x] = find(pa[x]);
}
bool uni(int p, int q){
p = find(p);
q = find(q);
if(p == q) return 0;
pa[p] = q;
return 1;
}
}disj;
int dx[4] = {1,0,-1,0}, dy[4] = {0,1,0,-1};
int qr(int s, int e){
if(dep[s] > dep[e]) swap(s,e);
int ret = 0, dx = dep[e] - dep[s];
for (int i=0; (1<<i)<=dx; i++) {
if(dx & (1<<i)){
ret = max(ret,val[e][i]);
e = pa[e][i];
}
}
for (int i=17; i>=0; i--) {
if(pa[s][i] != pa[e][i]){
ret = max(ret,val[s][i]);
ret = max(ret,val[e][i]);
s = pa[s][i];
e = pa[e][i];
}
}
if(s != e){
ret = max(ret,val[s][0]);
ret = max(ret,val[e][0]);
}
return ret;
}
vector<edg> cand;
queue<int> qx,qy;
void make_tree(){
for (int i=1; i<=p; i++) {
int px,py;
scanf("%d %d",&px,&py);
px--;
py--;
qx.push(px);
qy.push(py);
reg[px][py] = i;
dist[px][py] = 0;
}
while (!qx.empty()) {
int xf = qx.front();
int yf = qy.front();
qx.pop();
qy.pop();
for (int i=0; i<4; i++) {
if(xf + dx[i] < 0 || xf + dx[i] >= n || yf + dy[i] < 0 || yf + dy[i] >= m) continue;
if(str[xf+dx[i]][yf+dy[i]] == '#') continue;
if(reg[xf+dx[i]][yf+dy[i]]) continue;
reg[xf+dx[i]][yf+dy[i]] = reg[xf][yf];
dist[xf+dx[i]][yf+dy[i]] = dist[xf][yf] +1;
qx.push(xf + dx[i]);
qy.push(yf + dy[i]);
}
}
for (int i=0; i<n; i++) {
for (int j=0; j<m; j++) {
if(j + 1 != m && reg[i][j] != reg[i][j+1] && reg[i][j] && reg[i][j+1]){
cand.push_back({reg[i][j],reg[i][j+1],dist[i][j] + dist[i][j+1]});
}
if(i + 1 != n && reg[i][j] != reg[i+1][j] && reg[i][j] && reg[i+1][j]){
cand.push_back({reg[i][j],reg[i+1][j],dist[i][j] + dist[i+1][j]});
}
}
}
sort(cand.begin(),cand.end(),cmp);
for (int i=0; i<cand.size(); i++) {
if(disj.uni(cand[i].s,cand[i].e)){
graph[cand[i].s].push_back(pi(cand[i].x,cand[i].e));
graph[cand[i].e].push_back(pi(cand[i].x,cand[i].s));
}
}
for (int i=1; i<p; i++) {
if(disj.uni(i,i+1)){
graph[i].push_back(pi(1e9,i+1));
graph[i+1].push_back(pi(1e9,i));
}
}
}
void process_tree(){
qx.push(1);
qy.push(0);
while (!qx.empty()) {
int xf = qx.front();
int yf = qy.front();
for (int i=1; (1<<i) <= dep[xf]; i++) {
pa[xf][i] = pa[pa[xf][i-1]][i-1];
val[xf][i] = max(val[xf][i-1],val[pa[xf][i-1]][i-1]);
}
for (int i=0; i<graph[xf].size(); i++) {
int pos = graph[xf][i].second;
if(pos != yf){
pa[pos][0] = xf;
val[pos][0] = graph[xf][i].first;
dep[pos] = dep[xf] + 1;
}
}
}
}
int main(){
scanf("%d %d %d %d",&n,&m,&p,&q);
for (int i=0; i<n; i++) {
scanf("%s",str[i]);
}
disj.init(p);
make_tree();
process_tree();
for (int i=0; i<q; i++) {
int s,e;
scanf("%d %d",&s,&e);
int ret = qr(s,e);
if(ret > 1e8) puts("-1");
else printf("%d\n",ret);
}
}
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5000 ms |
71292 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5000 ms |
71700 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5000 ms |
71700 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
| # |
결과 |
실행 시간 |
메모리 |
Grader output |
| 1 |
Execution timed out |
5000 ms |
72236 KB |
Program timed out |
| 2 |
Halted |
0 ms |
0 KB |
- |
