結果
| 問題 | No.1326 ふたりのDominator |
| ユーザー |
 koba-e964
|
| 提出日時 | 2023-08-25 12:11:45 |
| 言語 | C++17 (gcc 12.3.0 + boost 1.83.0) |
| 結果 |
AC
|
| 実行時間 | 1,684 ms / 2,000 ms |
| コード長 | 7,924 bytes |
| コンパイル時間 | 3,476 ms |
| コンパイル使用メモリ | 163,128 KB |
| 実行使用メモリ | 51,772 KB |
| 最終ジャッジ日時 | 2024-06-06 06:49:58 |
| 合計ジャッジ時間 | 26,245 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
テストケース
テストケース表示| 入力 | 結果 | 実行時間 実行使用メモリ |
|---|---|---|
| testcase_00 | AC | 2 ms
6,812 KB |
| testcase_01 | AC | 3 ms
6,940 KB |
| testcase_02 | AC | 5 ms
6,940 KB |
| testcase_03 | AC | 5 ms
6,940 KB |
| testcase_04 | AC | 5 ms
6,944 KB |
| testcase_05 | AC | 2 ms
6,940 KB |
| testcase_06 | AC | 2 ms
6,944 KB |
| testcase_07 | AC | 17 ms
6,944 KB |
| testcase_08 | AC | 18 ms
6,940 KB |
| testcase_09 | AC | 17 ms
6,944 KB |
| testcase_10 | AC | 18 ms
6,940 KB |
| testcase_11 | AC | 18 ms
6,940 KB |
| testcase_12 | AC | 1,626 ms
31,120 KB |
| testcase_13 | AC | 1,589 ms
31,308 KB |
| testcase_14 | AC | 1,601 ms
31,332 KB |
| testcase_15 | AC | 1,608 ms
31,248 KB |
| testcase_16 | AC | 1,565 ms
30,572 KB |
| testcase_17 | AC | 1,476 ms
28,364 KB |
| testcase_18 | AC | 1,455 ms
30,928 KB |
| testcase_19 | AC | 1,453 ms
27,124 KB |
| testcase_20 | AC | 1,510 ms
43,516 KB |
| testcase_21 | AC | 1,612 ms
43,560 KB |
| testcase_22 | AC | 1,684 ms
51,772 KB |
| testcase_23 | AC | 1,543 ms
27,484 KB |
| testcase_24 | AC | 1,595 ms
31,372 KB |
ソースコード
#include <algorithm>
#include <cassert>
#include <cctype>
#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <functional>
#include <iomanip>
#include <iostream>
#include <list>
#include <map>
#include <queue>
#include <random>
#include <set>
#include <sstream>
#include <string>
#include <utility>
#include <vector>
#define REP(i,s,n) for(int i=(int)(s);i<(int)(n);i++)
#define DEBUGP(val) cerr << #val << "=" << val << "\n"
using namespace std;
typedef long long int ll;
typedef vector<int> VI;
typedef vector<ll> VL;
typedef pair<int, int> PI;
// Copied from https://kokiymgch.hatenablog.com/entry/2018/03/21/174958
//e2i[edge] -> index of the edge
//tree index : [0, 1, ..., bc.size() - 1] -> component
//tree index : [bc.size(), bc.size() + 1, ..., bc.size() + art.size() - 1] -> articulation
//cmp[index of edge] -> index of the node of the contructed tree
//cmp_node[index of node] -> -1 if it's not articulation, otherwise index of the node of the constructed tree
struct BiconnectedComponentTree {
vector<int> ord, low, art, cmp, cmp_node;
vector<bool> used;
vector<vector<int>> g, tree;
vector<vector<pair<int, int>>> bc;
vector<pair<int, int>> tmp;
map<pair<int, int>, int> e2i;
int n, m, k = 0;
BiconnectedComponentTree(const vector<vector<int>> &g, const map<pair<int, int>, int> &e2i) : g(g), e2i(e2i) {
n = g.size();
m = e2i.size();
cmp_node.resize(n, -1);
cmp.resize(m, -1);
ord.resize(n, -1);
low.resize(n, -1);
used.resize(n, false);
}
void dfs(int u, int prev) {
used[u] = true;
ord[u] = k ++;
low[u] = ord[u];
bool is_art = false;
int cnt = 0;
for (auto v : g[u]) if (v != prev) {
if (ord[v] < ord[u]) {
tmp.emplace_back(min(u, v), max(u, v));
}
if (!used[v]) {
cnt ++;
dfs(v, u);
low[u] = min(low[u], low[v]);
if (prev != -1 && low[v] >= ord[u]) {
is_art = true;
}
if (low[v] >= ord[u]) {
bc.push_back({});
while (true) {
pair<int, int> e = tmp.back();
bc.back().emplace_back(e);
tmp.pop_back();
if (min(u, v) == e.first && max(u, v) == e.second) {
break;
}
}
}
} else {
low[u] = min(low[u], ord[v]);
}
}
if (prev == -1 && cnt > 1) is_art = true;
if (is_art) art.push_back(u);
}
void build() {
dfs(0, -1);
for (int i = 0; i < (int) bc.size(); i ++) {
for (auto e : bc[i]) {
cmp[e2i[make_pair(min(e.first, e.second), max(e.first, e.second))]] = i;
}
}
tree.resize(bc.size() + art.size());
for (int i = 0; i < (int) art.size(); i ++) {
int j = i + (int) bc.size();
cmp_node[art[i]] = j;
int u = art[i];
set<int> tmp;
for (auto v : g[u]) {
int t = cmp[e2i[make_pair(min(u, v), max(u, v))]];
if (tmp.count(t) == 0) {
tmp.insert(t);
}
}
for (auto v : tmp) {
tree[j].push_back(v);
tree[v].push_back(j);
}
}
}
};
/**
* Lowest Common Ancestor. Call lca(x, y) to get the lca of them.
* Header Requirement: vector, cassert
* Verified by: AtCoder ABC014-D (http://abc014.contest.atcoder.jp/submissions/759125)
*/
class LowestCommonAncestor {
private:
int n, bn;
std::vector<int> parent; // 0 is root, parent[0] = 0
std::vector<int> dep;
// Lowest Common Ancestor
std::vector<std::vector<int> > lca_tbl;
void dfs(const std::vector<std::vector<int> > &edges, int v, int par, int d) {
parent[v] = par;
dep[v] = d;
for (int i = 0; i < edges[v].size(); ++i) {
int u = edges[v][i];
if (u != par) {
dfs(edges, u, v, d + 1);
}
}
}
void lca_init(void) {
for (int v = 0; v < n; ++v) {
lca_tbl[v] = std::vector<int>(bn + 1, 0);
lca_tbl[v][0] = parent[v];
}
for (int i = 1; i <= bn; ++i) {
for (int v = 0; v < n; ++v) {
lca_tbl[v][i] = lca_tbl[lca_tbl[v][i - 1]][i - 1];
}
}
}
public:
int lca(int x, int y) const {
int dx = dep[x];
int dy = dep[y];
if (dx > dy) {
return lca(y, x);
}
// Go up from y to the depth of x
for (int l = bn; l >= 0; --l) {
if (dy - dx >= 1 << l) {
y = lca_tbl[y][l];
dy -= 1 << l;
}
}
assert (dx == dy);
if (x == y) {
return x;
}
for (int l = bn; l >= 0; --l) {
if (lca_tbl[x][l] != lca_tbl[y][l]) {
x = lca_tbl[x][l];
y = lca_tbl[y][l];
}
}
return lca_tbl[x][0];
}
int depth(int a) const {
return dep[a];
}
LowestCommonAncestor(int n, const std::vector<std::vector<int> > &edges)
: n(n), parent(n), dep(n), lca_tbl(n) {
bn = 0;
while (n > 1 << bn) {
bn++;
}
dfs(edges, 0, 0, 0);
lca_init();
}
};
void dfs(int v, int par, const vector<VI> &g, int d, VI &dep) {
dep[v] = d;
for (int w: g[v]) {
if (w != par) dfs(w, v, g, d + 1, dep);
}
}
int main(void) {
ios::sync_with_stdio(false);
cin.tie(0);
int n, m;
cin >> n >> m;
vector<VI> g(n);
map<PI, int> e2i;
REP(i, 0, m) {
int u, v;
cin >> u >> v;
u--, v--;
g[u].push_back(v);
g[v].push_back(u);
e2i[PI(min(u, v), max(u, v))] = i;
}
BiconnectedComponentTree bct(g, e2i);
bct.build();
if (0) {
REP(i, 0, bct.cmp.size()) {
cerr << i << ": " << bct.cmp[i] << endl;
}
REP(i, 0, n) {
cerr << i << ": " << bct.cmp_node[i] << endl;
}
REP(i, 0, bct.tree.size()) {
cerr << i << ":";
for (int w: bct.tree[i]) cerr << " " << w;
cerr << endl;
}}
VI dep(bct.tree.size());
dfs(0, bct.tree.size(), bct.tree, 0, dep);
for (int v: dep) cerr << " " << v;
cerr << endl;
LowestCommonAncestor lca(bct.tree.size(), bct.tree);
int q;
cin >> q;
REP(_, 0, q) {
int x, y;
cin >> x >> y;
x--, y--;
if (x == y) {
cout << "0\n";
continue;
}
int bx = bct.cmp_node[x];
int by = bct.cmp_node[y];
if (bx < 0) {
int w = g[x][0];
int e = e2i[PI(min(x, w), max(x, w))];
bx = bct.cmp[e];
}
if (by < 0) {
int w = g[y][0];
int e = e2i[PI(min(y, w), max(y, w))];
by = bct.cmp[e];
}
cerr << "bx = " << bx << " by = " << by << endl;
int l = lca.lca(bx, by);
int dist = dep[bx] + dep[by] - 2 * dep[l];
cerr << "dist = " << dist << endl;
if (bct.cmp_node[x] >= 0) {
dist--;
}
if (bct.cmp_node[y] >= 0) {
dist--;
}
cout << dist / 2 << "\n";
}
}