解法
隣り合っている建物について辺を張って,最小全域木作って，Queryに早く答える。BFSすれば,隣り合っている建物がわかって嬉しい(経路中に建物をまたぐ移動は嬉しくないのは自明)
これでO(HW)。
それで,辺のコストが小さい順につないでいけば,最短距離がわかって(集合と集合がつながったタイミングのコスト)さらに嬉しい。俗に言う最小全域木。
この際に,俗に言うデータ構造をマージする一般的なテクを使ったら部分点70が生えた。
よくよく考えると、O(HW + HW log HW + (P log^2 Q)) ≒ O(2*10^8)くらい(適当)。
間に合ったりしても良さそうだけど,定数や入出力が重かったりしてわりとつらい。(←嘘ついた、マージしても間に合う。(下のソース)
さらに高速化を考えなければいけないんだけど、そのときにLCAを使うとよい。
最大値もダブリングして一緒に計算すれば,1つのクエリーに対数時間で答えることが出来て、 O(HW+HWlogHW+(P + Q)logP) ≒ O(10^8)になって,100点が生える。
ソース
#include<bits/stdc++.h>
using namespace std;
struct edge {
int u, v, cost;
bool operator<(const edge& e) const {
return cost < e.cost;
}
bool operator==(const edge& e) const {
return(u == e.u && v == e.v && cost == e.cost);
}
};
struct edge2 {
int to, cost;
};
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
typedef vector< edge > Edges;
typedef vector< vector< edge2 > > Graph;
const int INF = 1 << 30;
const int LOG_MAX = 20;
struct UnionFind {
vector< int > data;
UnionFind(int sz) {
data.assign( sz, -1);
}
int Union(int a, int b) {
a = Find(a), b = Find(b);
if(data[a] < data[b]) swap( a, b);
data[b] += data[a];
data[a] = b;
return(b);
}
int Find(int a) {
if(data[a] < 0) return(a);
else return(data[a] = Find(data[a]));
}
};
int H, W, P, Q;
int A[200000], B[200000], S[200000], T[200000];
bool mas[2000][2000];
Pi Number[2000][2000];
Edges edges;
Graph graph;
int Depth[200000];
int up[LOG_MAX][200000];
int upc[LOG_MAX][200000];
void bfs() {
queue< Pi > que;
static const int dy[] = { 0, 1, 0, -1}, dx[] = { 1, 0, -1, 0};
fill_n( *Number, 2000 * 2000, make_pair(-1, -1));
for(int i = 0; i < P; i++) {
que.push(make_pair(B[i], A[i]));
Number[A[i]][B[i]] = make_pair(0, i);
}
while(!que.empty()){
Pi p = que.front(); que.pop();
for(int i = 0; i < 4; i++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if(nx < 0 || ny < 0 || nx >= W || ny >= H || mas[ny][nx]) continue;
if(Number[ny][nx] != make_pair(-1, -1)) continue;
Number[ny][nx] = Number[p.second][p.first];
Number[ny][nx].first++;
que.push(make_pair(nx, ny));
}
}
return;
}
void make_graph() {
for(int i = 0; i < H; i++) {
for(int j = 0; j + 1 < W; j++) {
int u = Number[i][j].second, v = Number[i][j + 1].second;
if(u < 0 || v < 0 || u == v) continue;
int cost = Number[i][j].first + Number[i][j + 1].first;
edges.push_back((edge){u, v, cost});
}
}
for(int i = 0; i + 1 < H; i++) {
for(int j = 0; j < W; j++) {
int u = Number[i][j].second, v = Number[i + 1][j].second;
if(u < 0 || v < 0 || u == v) continue;
int cost = Number[i][j].first + Number[i + 1][j].first;
edges.push_back((edge){u, v, cost});
}
}
return;
}
void make_MST() {
graph.resize(P);
UnionFind uf(P);
sort( edges.begin(), edges.end());
edges.erase(unique(edges.begin(), edges.end()), edges.end());
for(int i = 0; i < edges.size(); i++){
edge& e = edges[i];
if(uf.Find(e.u) == uf.Find(e.v)) continue;
uf.Union( e.u, e.v);
graph[e.u].push_back((edge2){e.v, e.cost});
graph[e.v].push_back((edge2){e.u, e.cost});
}
for(int i = 1; i < P; i++) {
if(uf.Find(i - 1) == uf.Find(i)) continue;
graph[i - 1].push_back((edge2){i, INF});
graph[i].push_back((edge2){i - 1, INF});
uf.Union(i - 1, i);
}
}
int dfs(int idx, int prev, int cost) {
if(prev == -1) {
for(int i = 0; i < LOG_MAX; i++) {
up[i][idx] = -1;
}
Depth[idx] = 0;
} else {
up[0][idx] = prev, upc[0][idx] = cost;
Depth[idx] = Depth[prev] + 1;
for(int i = 1; i < LOG_MAX; i++) {
if(up[i - 1][idx] < 0) {
up[i][idx] = -1;
} else {
up[i][idx] = up[i - 1][up[i - 1][idx]];
upc[i][idx] = max( upc[i - 1][idx], upc[i - 1][up[i - 1][idx]]);
}
}
}
for(int i = 0; i < graph[idx].size(); i++) {
edge2& e = graph[idx][i];
if(e.to != prev) dfs( e.to, idx, e.cost);
}
}
void make_LCA() {
dfs( 0, -1, 0);
}
int queryLCA(int a, int b) {
if(Depth[a] > Depth[b]) swap(a, b);
int ret = 0;
for(int k = LOG_MAX - 1; k >= 0; --k) {
if((Depth[b] - Depth[a]) >> k & 1){
ret = max(ret, upc[k][b]);
b = up[k][b];
}
}
if(a == b) return(ret);
for(int k = LOG_MAX - 1; k >= 0; --k) {
if(up[k][a] != up[k][b]) {
ret = max( ret, max( upc[k][a], upc[k][b]));
a = up[k][a]; b = up[k][b];
}
}
return(max(ret, max(upc[0][a], upc[0][b])));
}
int main() {
scanf("%d %d %d %d", &H, &W, &P, &Q);
getchar();
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
char c;
scanf("%c", &c);
mas[i][j] = (c == '#');
}
getchar();
}
for(int i = 0; i < P; i++) {
scanf("%d %d", &A[i], &B[i]);
--A[i], --B[i];
}
for(int i = 0; i < Q; i++) {
scanf("%d %d", &S[i], &T[i]);
--S[i], --T[i];
}
bfs();
make_graph();
make_MST();
make_LCA();
int ret;
for(int i = 0; i < Q; i++){
printf("%d\n", (ret = queryLCA(S[i], T[i])) < INF ? ret : -1);
}
}
#include<bits/stdc++.h>
using namespace std;
struct edge {
int u, v, cost;
bool operator<(const edge& e) const {
return cost < e.cost;
}
bool operator==(const edge& e) {
return(u == e.u && v == e.v && cost == e.cost);
}
};
typedef pair< int, int > Pi;
typedef pair< int, Pi > Pii;
typedef vector< edge > Edges;
const int INF = 1 << 30;
int H, W, P, Q;
int A[200000], B[200000], S[200000], T[200000];
bool mas[2000][2000];
Pi Number[2000][2000];
set< int > data[200000];
Edges edges;
int answer[200000];
struct UnionFind {
vector< int > dat;
UnionFind(int sz) {
dat.assign( sz, -1);
}
int Union(int a, int b) {
a = Find(a), b = Find(b);
if(data[a].size() > data[b].size()) swap(a, b);
dat[b] += dat[a];
dat[a] = b;
return(b);
}
int Find(int a) {
if(dat[a] < 0) return(a);
else return(dat[a] = Find(dat[a]));
}
};
void bfs() {
queue< Pi > que;
static const int dy[] = { 0, 1, 0, -1}, dx[] = { 1, 0, -1, 0};
fill_n( *Number, 2000 * 2000, make_pair(-1, -1));
for(int i = 0; i < P; i++) {
que.push(make_pair(B[i], A[i]));
Number[A[i]][B[i]] = make_pair(0, i);
}
while(!que.empty()){
Pi p = que.front(); que.pop();
for(int i = 0; i < 4; i++) {
int nx = p.first + dx[i], ny = p.second + dy[i];
if(nx < 0 || ny < 0 || nx >= W || ny >= H || mas[ny][nx]) continue;
if(Number[ny][nx] != make_pair(-1, -1)) continue;
Number[ny][nx] = Number[p.second][p.first];
Number[ny][nx].first++;
que.push(make_pair(nx, ny));
}
}
return;
}
void make_graph() {
for(int i = 0; i < H; i++) {
for(int j = 0; j + 1 < W; j++) {
int u = Number[i][j].second, v = Number[i][j + 1].second;
if(u < 0 || v < 0 || u == v) continue;
int cost = Number[i][j].first + Number[i][j + 1].first;
edges.push_back((edge){u, v, cost});
}
}
for(int i = 0; i + 1 < H; i++) {
for(int j = 0; j < W; j++) {
int u = Number[i][j].second, v = Number[i + 1][j].second;
if(u < 0 || v < 0 || u == v) continue;
int cost = Number[i][j].first + Number[i + 1][j].first;
edges.push_back((edge){u, v, cost});
}
}
return;
}
int main() {
scanf("%d %d %d %d", &H, &W, &P, &Q);
getchar();
for(int i = 0; i < H; i++) {
for(int j = 0; j < W; j++) {
char c;
scanf("%c", &c);
mas[i][j] = (c == '#');
}
getchar();
}
for(int i = 0; i < P; i++) {
scanf("%d %d", &A[i], &B[i]);
--A[i], --B[i];
}
for(int i = 0; i < Q; i++) {
scanf("%d %d", &S[i], &T[i]);
--S[i], --T[i];
data[S[i]].insert(i);
data[T[i]].insert(i);
}
bfs();
make_graph();
sort( edges.begin(), edges.end());
edges.erase(unique(edges.begin(), edges.end()), edges.end());
UnionFind uf(P);
fill_n( answer, Q, -1);
for(int i = 0; i < edges.size(); i++){
edge& e = edges[i];
if((e.u = uf.Find(e.u)) == (e.v = uf.Find(e.v))) continue;
int unioned = uf.Union( e.u, e.v);
int u = e.u, v = e.v;
if(unioned == u) swap(u, v);
for(set< int >::iterator it = data[u].begin(); it != data[u].end(); ++it){
set< int >::iterator cell = data[v].find(*it);
if(cell != data[v].end()){ // あったらそのときのコストが解
answer[*it] = e.cost;
} else {
data[v].insert(*it);
}
}
}
for(int i = 0; i < Q; i++){
printf("%d\n", answer[i]);
}
}
0 件のコメント:
コメントを投稿