めるアイコン変換すると良さそうなのはすぐに思い至った。そこから繋げられずに editorial を見た。
問題概要
二次元平面上に 個の点がある。このうちの 2 点
が指定されている。その 2 点間のマンハッタン距離を
とする。
この 点について「マンハッタン距離が
である」ような二点について辺を張ったグラフを考える。このグラフの
を含む連結成分に含まれる辺の個数を求めよ。
制約
考えたこと
まず点 を中心としたマンハッタン距離が
の点集合というのは斜め正方形みたいになっている。これを 45 度回転させると「各軸に平行な正方形」になるのは周知の事実。
で、
- マンハッタン距離で考える
- L∞ 距離で考える
のどちらの方が考えやすいかは問題次第。でもいかにも今回みたいな設定だと、L∞ 距離の方が考えやすいんだろうなとなるよね。
つまったところ
この問題のグラフの辺が張られているところをピンポイントに探索すること自体は難しくない。
L∞ 距離で考えることにしたとき、点 からの距離が
の点のなす軌跡は各軸に平行な正方形なので、その四辺ごとにどの点が載っているのかを log オーダー程度で確認するのは難しくない。
問題は、このグラフが密グラフだったら結局 の計算時間がかかってしまう。
冷静に考えると...
ここからは editorial を見たけど単純だった！！！
DFS に付随して の計算量を要するのは、結局「一度見た頂点へと向かうような辺も探索するから」なのだ。
それをしなければよい！！！！！！
具体的には各座標を x 座標 y 座標ごとに整理してあげたとき、それを set で管理しておいて一度探索した頂点はその管理リストから削除するとするだけなのだ！！！！！
連結成分について頂点数ではなく辺数なので
最後の詰めは、上のように一度探索した頂点を削除すれば連結成分を求めるのには でできる。
しかしただこうしたのでは、連結成分に含まれる辺数の取得が難しい。これはでも実は簡単で
- 予めグラフの各頂点の次数を計算しておく
- そのためには今度は各座標を x 座標 y 座標ごとに分類して vector で管理する
とすればよい。なんかこの問題、ドンドンデータ構造が膨らんで怖い。。。
#include <iostream> #include <vector> #include <map> #include <set> #include <algorithm> #include <cmath> using namespace std; using pint = pair<int,int>; // 入力 int N, a, b; vector<int> vx, vy; map<pint,int> ptoi; // 整理 map<int, set<int>> xy, yx; map<int, vector<int>> vxy, vyx; long long D, res; vector<long long> deg; vector<bool> seen; void dfs(int v) { res += deg[v]; seen[v] = true; int x = vx[v], y = vy[v]; vector<int> nvs; // 右側 { auto &se = xy[x + D]; auto it = se.lower_bound(y - D); for (; it != se.end() && *it <= y + D; it = se.erase(it)) nvs.push_back(ptoi[{x+D, *it}]), yx[*it].erase(x+D); } // 左側 { auto &se = xy[x - D]; auto it = se.lower_bound(y - D); for (; it != se.end() && *it <= y + D; it = se.erase(it)) nvs.push_back(ptoi[{x-D, *it}]), yx[*it].erase(x-D); } // 上側 { auto &se = yx[y + D]; auto it = se.lower_bound(x - D); for (; it != se.end() && *it <= x + D; it = se.erase(it)) nvs.push_back(ptoi[{*it, y+D}]), xy[*it].erase(y+D); } // 下側 { auto &se = yx[y - D]; auto it = se.lower_bound(x - D); for (; it != se.end() && *it <= x + D; it = se.erase(it)) nvs.push_back(ptoi[{*it, y-D}]), xy[*it].erase(y-D); } // 探索 for (auto nv : nvs) if (!seen[nv]) dfs(nv); } long long solve() { D = max(abs(vx[a] - vx[b]), abs(vy[a] - vy[b])); // 次数を求める deg.assign(N, 0); for (int i = 0; i < N; ++i) { int x = vx[i], y = vy[i]; deg[i] += upper_bound(vxy[x + D].begin(), vxy[x + D].end(), y + D) - lower_bound(vxy[x + D].begin(), vxy[x + D].end(), y - D); deg[i] += upper_bound(vxy[x - D].begin(), vxy[x - D].end(), y + D) - lower_bound(vxy[x - D].begin(), vxy[x - D].end(), y - D); deg[i] += upper_bound(vyx[y + D].begin(), vyx[y + D].end(), x + D) - lower_bound(vyx[y + D].begin(), vyx[y + D].end(), x - D); deg[i] += upper_bound(vyx[y - D].begin(), vyx[y - D].end(), x + D) - lower_bound(vyx[y - D].begin(), vyx[y - D].end(), x - D); if (ptoi.count(pint(x+D, y+D))) --deg[i]; if (ptoi.count(pint(x+D, y-D))) --deg[i]; if (ptoi.count(pint(x-D, y+D))) --deg[i]; if (ptoi.count(pint(x-D, y-D))) --deg[i]; } // 連結成分のみを探索 res = 0; seen.assign(N, 0); dfs(a); return res/2; } int main() { while (cin >> N >> a >> b) { --a, --b; vx.resize(N); vy.resize(N); ptoi.clear(); xy.clear(), yx.clear(), vxy.clear(), vyx.clear(); for (int i = 0; i < N; ++i) { int x, y; cin >> x >> y; vx[i] = x + y, vy[i] = x - y; ptoi[pint(vx[i],vy[i])] = i; xy[vx[i]].insert(vy[i]); yx[vy[i]].insert(vx[i]); vxy[vx[i]].push_back(vy[i]); vyx[vy[i]].push_back(vx[i]); } for (auto &it : vxy) sort(it.second.begin(), it.second.end()); for (auto &it : vyx) sort(it.second.begin(), it.second.end()); cout << solve() << endl; } }
