社区讨论
UOJ extra test #13 WA 求助！！
P6777[NOI2020] 翻修道路【数据有误】参与者 1已保存回复 0
讨论操作
快速查看讨论及其快照的属性，并进行相关操作。
- 当前回复
- 0 条
- 当前快照
- 1 份
- 快照标识符
- @mhjb1010
- 此快照首次捕获于
- 2025/11/03 23:38 4 个月前
- 此快照最后确认于
- 2025/11/03 23:38 4 个月前
是的你谷时限3s但是我卡不进去跑去uoj了，然后发现extra test挂了 /kk
有点怀疑是不是数据问题（不是弦图），但是并没有手段弄到这组数据（
乱调有时候其他点还是能过，这个点照样挂，但是挂的不一样（）
CPPinput:
500000 999999
345456 284393 824783628
374245 447248 355326905
5991 162792 552011142
309015 80686 923...
output:
21956719471026
result:
wrong answer 1st numbers differ - expected: '21616787411556', found: '21956719471026'
#include <algorithm>
#include <array>
#include <cstdint>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <iterator>
#include <limits>
#include <numeric>
#include <queue>
#include <unordered_map>
#include <unordered_set>
#include <utility>
#include <vector>
#if defined(__GNUC__) && !defined(__clang__)
#pragma GCC optimize("O3")
#pragma GCC target("avx2")
#pragma GCC optimize("unroll-loops")
#endif
inline size_t next_power_of_2(size_t n) {
if (n <= 1)
return 1;
return 1ull << (64 - __builtin_clzll(n - 1));
}
using namespace std;
constexpr int64_t INF = numeric_limits<int64_t>::max();
constexpr int32_t INF_INT = numeric_limits<int32_t>::max();
typedef int32_t Vertex;
typedef vector<Vertex> Path;
using BoolVector = vector<uint8_t>;
constexpr Vertex V_NONE = 0;
typedef uint64_t PackedKey;
struct optimized_hash {
static uint64_t splitmix64(uint64_t x) {
x += 0x9e3779b97f4a7c15;
x = (x ^ (x >> 30)) * 0xbf58476d1ce4e5b9;
x = (x ^ (x >> 27)) * 0x94d049bb133111eb;
return x ^ (x >> 31);
}
template <typename T> size_t operator()(T x) const {
static const uint64_t FIXED_RANDOM =
reinterpret_cast<uint64_t>(&FIXED_RANDOM);
return splitmix64(static_cast<uint64_t>(x) + FIXED_RANDOM);
}
};
inline PackedKey edge_key(Vertex u, Vertex v) {
if (u > v)
swap(u, v);
return ((uint64_t)v << 32) | (uint32_t)u;
}
inline PackedKey directed_edge_key(Vertex u, Vertex v) {
return ((uint64_t)u << 32) | (uint32_t)v;
}
inline PackedKey lr_key(int32_t r_id, Vertex u) {
return ((uint64_t)r_id << 32) | (uint32_t)u;
}
inline pair<Vertex, Vertex> unpack_edge_key(PackedKey key) {
return {(Vertex)(key & 0xFFFFFFFF), (Vertex)(key >> 32)};
}
template <typename V>
using OptimizedMap = unordered_map<PackedKey, V, optimized_hash>;
template <typename K> using OptimizedSet = unordered_set<K, optimized_hash>;
struct FlatMap {
struct Slot {
PackedKey k;
uint32_t v_plus1;
};
vector<Slot> tab;
vector<uint8_t> used;
size_t mask = 0;
void init(size_t capacity_estimate) {
if (capacity_estimate == 0) {
mask = 0;
return;
}
size_t cap_pow2 =
next_power_of_2(capacity_estimate + capacity_estimate / 2);
if (cap_pow2 < 16)
cap_pow2 = 16;
if (cap_pow2 == 0) {
mask = 0;
return;
}
tab.assign(cap_pow2, {});
used.assign(cap_pow2, 0);
mask = cap_pow2 - 1;
}
inline void set(PackedKey k, Vertex v) {
if (mask == 0)
return;
size_t i = optimized_hash::splitmix64(k) & mask;
while (used[i] && tab[i].k != k)
i = (i + 1) & mask;
if (!used[i]) {
used[i] = 1;
tab[i].k = k;
}
tab[i].v_plus1 = (uint32_t)v + 1u;
}
inline bool try_get(PackedKey k, Vertex& out) const {
if (mask == 0)
return false;
size_t i = optimized_hash::splitmix64(k) & mask;
while (used[i]) {
if (tab[i].k == k) {
out = (Vertex)(tab[i].v_plus1 - 1u);
return true;
}
i = (i + 1) & mask;
}
return false;
}
};
struct Edge {
int64_t weight;
Vertex to;
int32_t id;
};
struct OriginalEdge {
Vertex u, v;
int64_t weight;
int32_t id;
OriginalEdge(Vertex u, Vertex v, int64_t w, int32_t id)
: u(u), v(v), weight(w), id(id) {}
};
class Graph {
public:
vector<vector<Edge>> adj;
int32_t N;
bool finalized = false;
vector<OriginalEdge> edge_storage;
vector<const OriginalEdge*> edge_list;
vector<const OriginalEdge*> edge_id_to_ptr;
int32_t max_edge_id = -1;
Graph() : N(0) {}
Graph(int32_t vertex_count, int32_t edge_count) {
N = vertex_count + 1;
adj.resize(N);
if (edge_count > 0) {
edge_storage.reserve(edge_count);
edge_list.reserve(edge_count);
edge_id_to_ptr.reserve(edge_count);
}
}
void finalize_construction() {
if (finalized)
return;
for (Vertex u = 1; u < N; ++u) {
sort(adj[u].begin(), adj[u].end(),
[](const Edge& a, const Edge& b) { return a.to < b.to; });
}
finalized = true;
}
void ensure_vertex_capacity(Vertex u) {
if (u >= N) {
N = u + 1;
adj.resize(N);
finalized = false;
}
}
void ensure_id_capacity(int32_t id) {
if (id != -1 && id >= static_cast<int32_t>(edge_id_to_ptr.size())) {
edge_id_to_ptr.resize(id + 1, nullptr);
}
}
void add_directed_edge(Vertex u, Vertex v, int64_t w, int32_t id) {
adj[u].push_back({w, v, id});
}
void add_edge(Vertex u, Vertex v, int64_t w, int32_t id,
const OriginalEdge* existing_ptr = nullptr) {
if (id != -1) {
if (id > max_edge_id) {
max_edge_id = id;
ensure_id_capacity(id);
} else if (id >= static_cast<int32_t>(edge_id_to_ptr.size())) {
ensure_id_capacity(id);
}
if (id < static_cast<int32_t>(edge_id_to_ptr.size()) &&
edge_id_to_ptr[id]) {
return;
}
}
if (max(u, v) >= N) {
ensure_vertex_capacity(max(u, v));
}
add_directed_edge(u, v, w, id);
add_directed_edge(v, u, w, id);
finalized = false;
if (id != -1) {
const OriginalEdge* ptr;
if (existing_ptr) {
ptr = existing_ptr;
} else {
edge_storage.emplace_back(u, v, w, id);
ptr = &edge_storage.back();
}
edge_list.push_back(ptr);
if (id < static_cast<int32_t>(edge_id_to_ptr.size())) {
edge_id_to_ptr[id] = ptr;
}
}
}
inline pair<int64_t, int32_t> get_edge_info(Vertex u, Vertex v) const {
if (u >= N || v >= N || u == 0 || v == 0)
return {INF, -1};
const vector<Edge>* adj_list;
Vertex target;
if (adj[u].size() <= adj[v].size()) {
adj_list = &adj[u];
target = v;
} else {
adj_list = &adj[v];
target = u;
}
if (finalized) {
auto it = std::lower_bound(
adj_list->begin(), adj_list->end(), target,
[](const Edge& e, Vertex t) { return e.to < t; });
if (it != adj_list->end() && it->to == target) {
return {it->weight, it->id};
}
} else {
for (const auto& edge : *adj_list) {
if (edge.to == target) {
return {edge.weight, edge.id};
}
}
}
return {INF, -1};
}
bool are_adjacent(Vertex u, Vertex v) const {
return get_edge_info(u, v).second != -1;
}
const OriginalEdge* get_edge_ptr(int32_t id) const {
if (id < 0 || id >= static_cast<int32_t>(edge_id_to_ptr.size()))
return nullptr;
return edge_id_to_ptr[id];
}
};
class MultiGraph {
public:
vector<vector<pair<Vertex, int32_t>>> adj;
int32_t N;
MultiGraph(int32_t size) : N(size) { adj.resize(N); }
};
inline int64_t get_edge_length(const Graph& G, Vertex u, Vertex v) {
return G.get_edge_info(u, v).first;
}
inline int32_t get_edge_id(const Graph& G, Vertex u, Vertex v) {
return G.get_edge_info(u, v).second;
}
inline vector<int32_t> get_P_indices_vec(const Path& P, int32_t N) {
vector<int32_t> indices(N, -1);
for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
if (P[i] > 0 && P[i] < N) {
indices[P[i]] = i;
}
}
return indices;
}
inline bool is_useful_weighted(const Path& r, const vector<int64_t>& weights,
const Graph& G) {
if (r.size() < 3)
return false;
for (int32_t i = 0; i <= static_cast<int32_t>(r.size()) - 3; ++i) {
int64_t len_path = weights[i] + weights[i + 1];
int64_t len_edge = get_edge_length(G, r[i], r[i + 2]);
if (len_edge != INF && len_path >= len_edge) {
return false;
}
}
return true;
}
template <class Key, class Val> struct RadixHeap64 {
static_assert(std::is_unsigned<Key>::value, "Key must be unsigned");
array<vector<pair<Key, Val>>, 65> b;
Key last = 0;
size_t sz = 0;
static int bucket_id(Key x, Key y) {
return x == y ? 0 : (64 - __builtin_clzll(x ^ y));
}
void push(Key k, const Val& v) {
int id = bucket_id(k, last);
b[id].push_back({k, v});
++sz;
}
bool empty() const { return sz == 0; }
pair<Key, Val> top() {
if (b[0].empty()) {
int i = 1;
while (b[i].empty())
++i;
Key new_last = numeric_limits<Key>::max();
for (auto& kv : b[i])
new_last = min(new_last, kv.first);
for (auto& kv : b[i]) {
int id = bucket_id(kv.first, new_last);
b[id].push_back(kv);
}
b[i].clear();
last = new_last;
}
auto& vec = b[0];
auto res = vec.back();
return res;
}
void pop() {
auto& vec = b[0];
vec.pop_back();
--sz;
}
};
pair<int64_t, Path> dijkstra(const Graph& G, Vertex S, Vertex T,
const BoolVector& forbid_v = {},
const BoolVector& forbid_e = {}) {
if (S <= 0 || S >= G.N || T <= 0 || T >= G.N)
return {INF, {}};
if (!forbid_v.empty() && ((S < (int)forbid_v.size() && forbid_v[S]) ||
(T < (int)forbid_v.size() && forbid_v[T])))
return {INF, {}};
vector<int64_t> dist(G.N, INF);
vector<Vertex> parent(G.N, V_NONE);
RadixHeap64<uint64_t, Vertex> pq;
dist[S] = 0;
pq.push(0, S);
while (!pq.empty()) {
auto [d, u] = pq.top();
pq.pop();
if ((int64_t)d != dist[u])
continue;
if (u == T)
break;
for (const auto& e : G.adj[u]) {
Vertex v = e.to;
if (!forbid_v.empty() && v < (int)forbid_v.size() && forbid_v[v])
continue;
if (e.id != -1 && !forbid_e.empty() &&
e.id < (int)forbid_e.size() && forbid_e[e.id])
continue;
int64_t nd = dist[u] + e.weight;
if (nd < dist[v]) {
dist[v] = nd;
parent[v] = u;
pq.push((uint64_t)nd, v);
}
}
}
if (dist[T] == INF)
return {INF, {}};
Path path;
for (Vertex cur = T; cur != S; cur = parent[cur]) {
if (cur == V_NONE)
return {INF, {}};
path.push_back(cur);
}
path.push_back(S);
reverse(path.begin(), path.end());
return {dist[T], path};
}
class BridgeFinder {
public:
const Graph& G;
vector<int32_t> tin, low;
int timer;
BoolVector is_bridge;
int max_id = -1;
BridgeFinder(const Graph& G) : G(G) {}
struct DFSState {
Vertex v;
Vertex p;
int edge_id_in;
size_t neighbor_index;
};
inline void find_Bridges() {
timer = 0;
tin.assign(G.N, -1);
low.assign(G.N, -1);
vector<int32_t> bridge_ids_vec;
bridge_ids_vec.reserve(G.edge_list.size());
vector<DFSState> stack;
if (G.N > 1)
stack.reserve(G.N);
for (Vertex start_node = 1; start_node < G.N; ++start_node) {
if (tin[start_node] != -1)
continue;
stack.push_back({start_node, V_NONE, -1, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = G.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge = adj_v[state.neighbor_index];
Vertex to = edge.to;
state.neighbor_index++;
if (to == state.p)
continue;
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
} else {
stack.push_back({to, state.v, edge.id, 0});
pushed_child = true;
break;
}
}
if (pushed_child) {
continue;
}
Vertex v = state.v;
Vertex p = state.p;
int32_t edge_id_in = state.edge_id_in;
stack.pop_back();
if (p != V_NONE) {
low[p] = min(low[p], low[v]);
if (low[v] > tin[p]) {
if (edge_id_in != -1) {
bridge_ids_vec.push_back(edge_id_in);
if (edge_id_in > max_id) {
max_id = edge_id_in;
}
}
}
}
}
}
if (max_id != -1) {
is_bridge.assign(max_id + 1, false);
for (int32_t id : bridge_ids_vec) {
is_bridge[id] = true;
}
}
}
};
class BCCFinder {
public:
const Graph& G;
const BoolVector* forbidden_edge_ids = nullptr;
vector<int32_t> tin, low;
int32_t timer;
vector<vector<Vertex>> BCCs;
vector<int> mark_v_internal;
int stamp_counter_internal;
vector<vector<int32_t>> vertex_BCC_membership;
BoolVector is_ap;
vector<int32_t> edge_stack;
vector<int32_t> edge_to_BCC;
BCCFinder(const Graph& G, const BoolVector* forbidden = nullptr)
: G(G), forbidden_edge_ids(forbidden) {}
struct DFSState {
Vertex v;
Vertex p;
int32_t edge_id_in;
size_t neighbor_index;
int32_t children_count;
};
inline void find_BCCs() {
timer = 0;
tin.assign(G.N, -1);
low.assign(G.N, -1);
BCCs.clear();
stamp_counter_internal = 1;
mark_v_internal.assign(G.N, 0);
vertex_BCC_membership.assign(G.N, {});
is_ap.assign(G.N, false);
edge_stack.clear();
edge_stack.reserve(G.edge_list.size());
if (G.max_edge_id != -1) {
edge_to_BCC.assign(G.max_edge_id + 1, -1);
} else {
edge_to_BCC.clear();
}
vector<DFSState> stack;
if (G.N > 1)
stack.reserve(G.N);
for (Vertex start_node = 1; start_node < G.N; ++start_node) {
if (tin[start_node] != -1)
continue;
stack.push_back({start_node, V_NONE, -1, 0, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = G.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge = adj_v[state.neighbor_index];
Vertex to = edge.to;
state.neighbor_index++;
if (to == state.p)
continue;
if (forbidden_edge_ids && edge.id != -1 &&
edge.id <
static_cast<int32_t>(forbidden_edge_ids->size()) &&
(*forbidden_edge_ids)[edge.id]) {
continue;
}
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
if (tin[to] < tin[state.v]) {
if (edge.id != -1) {
edge_stack.push_back(edge.id);
}
}
} else {
if (edge.id != -1) {
edge_stack.push_back(edge.id);
}
stack.push_back({to, state.v, edge.id, 0, 0});
pushed_child = true;
break;
}
}
if (pushed_child) {
continue;
}
Vertex v = state.v;
Vertex p = state.p;
int32_t edge_id_in = state.edge_id_in;
int32_t children_count = state.children_count;
stack.pop_back();
if (p != V_NONE) {
DFSState& parent_state = stack.back();
parent_state.children_count++;
low[p] = min(low[p], low[v]);
if (low[v] >= tin[p]) {
if (parent_state.p != V_NONE) {
is_ap[p] = true;
}
int32_t bcc_index = BCCs.size();
vector<Vertex> component_vertices_with_dups;
int32_t critical_edge_id = edge_id_in;
while (!edge_stack.empty()) {
int32_t e_id = edge_stack.back();
bool is_critical = (e_id == critical_edge_id);
edge_stack.pop_back();
const OriginalEdge* e_ptr = G.get_edge_ptr(e_id);
if (e_ptr) {
component_vertices_with_dups.push_back(
e_ptr->u);
component_vertices_with_dups.push_back(
e_ptr->v);
}
if (e_id != -1 && e_id < static_cast<int32_t>(
edge_to_BCC.size())) {
edge_to_BCC[e_id] = bcc_index;
}
if (is_critical)
break;
}
if (!component_vertices_with_dups.empty()) {
vector<Vertex> component;
component.reserve(
component_vertices_with_dups.size());
stamp_counter_internal++;
for (Vertex u : component_vertices_with_dups) {
if (u < G.N && mark_v_internal[u] !=
stamp_counter_internal) {
mark_v_internal[u] = stamp_counter_internal;
component.push_back(u);
if (u < static_cast<Vertex>(
vertex_BCC_membership.size())) {
vertex_BCC_membership[u].push_back(
bcc_index);
}
}
}
if (!component.empty()) {
BCCs.push_back(std::move(component));
}
}
}
} else {
if (children_count > 1) {
is_ap[v] = true;
}
}
}
}
for (auto& membership_list : vertex_BCC_membership) {
std::sort(membership_list.begin(), membership_list.end());
}
}
inline bool is_in_BCC(int bcc_idx, Vertex v) const {
if (v <= 0 || v >= G.N)
return false;
if (bcc_idx < 0 || bcc_idx >= (int)BCCs.size())
return false;
const auto& ms = vertex_BCC_membership[v];
return std::binary_search(ms.begin(), ms.end(), bcc_idx);
}
};
class BCCFinder_Multi {
public:
const MultiGraph& MG;
vector<int32_t> tin, low;
int32_t timer;
vector<vector<int32_t>> BCC_edges;
vector<int32_t> edge_stack;
BCCFinder_Multi(const MultiGraph& MG) : MG(MG) {}
struct DFSState {
Vertex v;
Vertex p;
int32_t parent_edge_id;
size_t neighbor_index;
};
inline void find_BCCs() {
timer = 0;
tin.assign(MG.N, -1);
low.assign(MG.N, -1);
BCC_edges.clear();
edge_stack.clear();
vector<DFSState> stack;
if (MG.N > 1)
stack.reserve(MG.N);
for (Vertex start_node = 1; start_node < MG.N; ++start_node) {
if (tin[start_node] != -1)
continue;
if (MG.adj[start_node].empty())
continue;
stack.push_back({start_node, V_NONE, -1, 0});
while (!stack.empty()) {
DFSState& state = stack.back();
if (state.neighbor_index == 0) {
if (tin[state.v] == -1) {
tin[state.v] = low[state.v] = timer++;
}
}
const auto& adj_v = MG.adj[state.v];
bool pushed_child = false;
while (state.neighbor_index < adj_v.size()) {
const auto& edge_info = adj_v[state.neighbor_index];
Vertex to = edge_info.first;
int32_t current_edge_id = edge_info.second;
state.neighbor_index++;
if (current_edge_id == state.parent_edge_id)
continue;
if (tin[to] != -1) {
low[state.v] = min(low[state.v], tin[to]);
if (tin[to] < tin[state.v]) {
edge_stack.push_back(current_edge_id);
}
} else {
edge_stack.push_back(current_edge_id);
stack.push_back({to, state.v, current_edge_id, 0});
pushed_child = true;
break;
}
}
if (pushed_child)
continue;
Vertex v = state.v;
Vertex p = state.p;
int32_t parent_edge_id = state.parent_edge_id;
stack.pop_back();
if (p != V_NONE) {
low[p] = min(low[p], low[v]);
if (low[v] >= tin[p]) {
vector<int32_t> component;
while (!edge_stack.empty()) {
int32_t e_id = edge_stack.back();
edge_stack.pop_back();
component.push_back(e_id);
if (e_id == parent_edge_id)
break;
}
if (!component.empty()) {
BCC_edges.push_back(std::move(component));
}
}
}
}
}
}
};
struct BCTree {
int32_t N;
vector<vector<int32_t>> adj;
int32_t get_ap_id(Vertex v) const { return v; }
int32_t get_bcc_id(int32_t i) const { return N + i; }
inline void build(const BCCFinder& bcc_finder, int32_t graph_N) {
N = graph_N;
const auto& BCCs = bcc_finder.BCCs;
const auto& is_ap = bcc_finder.is_ap;
int32_t total_nodes = N + BCCs.size();
adj.clear();
adj.resize(total_nodes);
for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
int32_t bcc_id = get_bcc_id(i);
for (Vertex v : BCCs[i]) {
if (v < static_cast<int32_t>(is_ap.size()) && is_ap[v]) {
int32_t ap_id = get_ap_id(v);
adj[bcc_id].push_back(ap_id);
adj[ap_id].push_back(bcc_id);
}
}
}
}
inline vector<int32_t> find_path(int32_t start_node, int32_t end_node) {
if (start_node == -1 || end_node == -1)
return {};
if (start_node == end_node)
return {start_node};
int32_t total_nodes = adj.size();
if (start_node >= total_nodes || end_node >= total_nodes ||
start_node <= 0 || end_node <= 0)
return {};
queue<int32_t> q;
vector<int32_t> parent(total_nodes, -1);
q.push(start_node);
parent[start_node] = 0;
bool found = false;
while (!q.empty()) {
int32_t u = q.front();
q.pop();
if (u == end_node) {
found = true;
break;
}
for (const int v : adj[u]) {
if (parent[v] == -1) {
parent[v] = u;
q.push(v);
}
}
}
if (!found)
return {};
vector<int32_t> path;
int32_t curr = end_node;
while (curr != 0) {
path.push_back(curr);
curr = parent[curr];
}
reverse(path.begin(), path.end());
return path;
}
};
inline BoolVector compute_BAD_G(const Graph& G, Vertex S, Vertex T) {
BCCFinder bcc_finder(G);
bcc_finder.find_BCCs();
BCTree bct;
bct.build(bcc_finder, G.N);
const auto& is_ap = bcc_finder.is_ap;
const auto& BCCs = bcc_finder.BCCs;
vector<int32_t> vertex_to_bcc(G.N, -1);
for (int32_t i = 0; i < static_cast<int32_t>(BCCs.size()); ++i) {
for (Vertex v : BCCs[i]) {
if (v < G.N &&
(v >= static_cast<int32_t>(is_ap.size()) || !is_ap[v])) {
vertex_to_bcc[v] = i;
}
}
}
auto find_tau = [&](Vertex V) {
if (V <= 0 || V >= G.N)
return -1;
if (V < static_cast<int32_t>(is_ap.size()) && is_ap[V]) {
return bct.get_ap_id(V);
} else {
int32_t bcc_index = vertex_to_bcc[V];
if (bcc_index != -1)
return bct.get_bcc_id(bcc_index);
}
return -1;
};
int32_t S_tau = find_tau(S);
int32_t T_tau = find_tau(T);
vector<int32_t> path = bct.find_path(S_tau, T_tau);
BoolVector is_bad(G.N, false);
vector<int32_t> degrees_in_C_dat(G.N, 0);
BoolVector in_C_ws(G.N, false);
for (int32_t index = 0; index < static_cast<int32_t>(path.size());
++index) {
const int32_t node_id = path[index];
if (node_id >= G.N) {
int32_t bcc_index = node_id - G.N;
if (bcc_index < 0 || bcc_index >= static_cast<int32_t>(BCCs.size()))
continue;
const auto& C = BCCs[bcc_index];
for (Vertex v : C) {
if (v < G.N)
in_C_ws[v] = true;
}
for (Vertex u : C) {
int32_t degree = 0;
if (u < G.N) {
for (const auto& edge : G.adj[u]) {
if (edge.to < G.N && in_C_ws[edge.to])
degree++;
}
degrees_in_C_dat[u] = degree;
}
}
for (Vertex u : C) {
if (u == S || u == T || u >= G.N)
continue;
if (degrees_in_C_dat[u] == 2) {
bool u_is_AP_connector = false;
if (u < static_cast<int32_t>(is_ap.size()) && is_ap[u]) {
int32_t u_ap_id = bct.get_ap_id(u);
if (index > 0 && path[index - 1] == u_ap_id) {
u_is_AP_connector = true;
}
if (!u_is_AP_connector &&
index < static_cast<int32_t>(path.size()) - 1 &&
path[index + 1] == u_ap_id) {
u_is_AP_connector = true;
}
}
if (!u_is_AP_connector) {
is_bad[u] = true;
}
}
}
for (Vertex v : C) {
if (v < G.N)
in_C_ws[v] = false;
}
}
}
return is_bad;
}
struct DSU {
vector<int> fa, sz;
DSU(int n = 0) { init(n); }
void init(int n) {
fa.resize(n);
sz.assign(n, 1);
std::iota(fa.begin(), fa.end(), 0);
}
int find(int x) {
while (fa[x] != x) {
fa[x] = fa[fa[x]];
x = fa[x];
}
return x;
}
void unite(int a, int b) {
a = find(a);
b = find(b);
if (a == b)
return;
if (sz[a] < sz[b])
swap(a, b);
fa[b] = a;
sz[a] += sz[b];
}
};
inline Path validate_separator(const vector<const OriginalEdge*>& R,
const Graph& G, bool required_odd_P_index,
const vector<int32_t>& P_indices,
const vector<int32_t>& min_P_neighbor_index,
vector<vector<pair<Vertex, int64_t>>>& adj_R_ws,
BoolVector& in_R_ws) {
if (R.empty())
return {};
const int32_t N = G.N;
vector<Vertex> vertices_R;
vertices_R.reserve(R.size() + 1);
for (const auto* edge_ptr : R) {
Vertex u = edge_ptr->u;
Vertex v = edge_ptr->v;
int64_t w = edge_ptr->weight;
if (u >= N || v >= N || u == 0 || v == 0)
continue;
adj_R_ws[u].push_back({v, w});
adj_R_ws[v].push_back({u, w});
if (!in_R_ws[u]) {
in_R_ws[u] = true;
vertices_R.push_back(u);
}
if (!in_R_ws[v]) {
in_R_ws[v] = true;
vertices_R.push_back(v);
}
}
auto cleanup = [&]() {
for (Vertex v : vertices_R) {
in_R_ws[v] = false;
adj_R_ws[v].clear();
}
};
vector<Vertex> endpoints;
for (Vertex v : vertices_R) {
const auto& neighbors = adj_R_ws[v];
if (neighbors.size() > 2) {
cleanup();
return {};
}
if (neighbors.size() == 1)
endpoints.push_back(v);
}
if (endpoints.size() != 2) {
cleanup();
return {};
}
Path r;
vector<int64_t> r_weights;
r.reserve(R.size() + 1);
r_weights.reserve(R.size());
Vertex curr = endpoints[0];
Vertex prev = V_NONE;
while (curr != V_NONE) {
r.push_back(curr);
Vertex next = V_NONE;
const auto& neighbors = adj_R_ws[curr];
for (const auto& edge_info : neighbors) {
Vertex neighbor = edge_info.first;
int64_t weight = edge_info.second;
if (neighbor != prev) {
next = neighbor;
r_weights.push_back(weight);
break;
}
}
prev = curr;
curr = next;
}
cleanup();
if (r.size() != R.size() + 1)
return {};
auto check_alignment = [&](const Path& path) {
int32_t last_P_idx = -1;
for (Vertex v : path) {
if (v < static_cast<int32_t>(P_indices.size()) &&
P_indices[v] != -1) {
if (P_indices[v] <= last_P_idx)
return false;
last_P_idx = P_indices[v];
}
}
return true;
};
if (!check_alignment(r)) {
reverse(r.begin(), r.end());
reverse(r_weights.begin(), r_weights.end());
if (!check_alignment(r))
return {};
}
if (r.size() < 4)
return {};
for (size_t i = 2; i < r.size(); ++i) {
if (r[i] >= static_cast<int32_t>(P_indices.size()) ||
P_indices[r[i]] == -1)
return {};
}
int32_t idx_r2 = P_indices[r[2]];
if ((idx_r2 % 2 != 0) != required_odd_P_index)
return {};
if (!is_useful_weighted(r, r_weights, G))
return {};
Vertex r0 = r[0];
bool traversable = false;
if (r0 < static_cast<int32_t>(P_indices.size()) && P_indices[r0] != -1) {
if (P_indices[r0] < idx_r2)
traversable = true;
}
if (!traversable) {
if (r0 < static_cast<int32_t>(min_P_neighbor_index.size()) &&
min_P_neighbor_index[r0] != INF_INT) {
if (min_P_neighbor_index[r0] < idx_r2)
traversable = true;
}
}
if (!traversable)
return {};
return r;
}
inline void compute_S_Separators(const Graph& G, const Path& P,
vector<Path>& X_result) {
if (P.empty())
return;
vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
vector<int32_t> min_P_neighbor_index(G.N, INF_INT);
for (int32_t i = 0; i < static_cast<int32_t>(P.size()); ++i) {
Vertex u = P[i];
if (u >= G.N || u == 0)
continue;
if (i < min_P_neighbor_index[u])
min_P_neighbor_index[u] = i;
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (i < min_P_neighbor_index[v])
min_P_neighbor_index[v] = i;
}
}
BoolVector adj2;
if (P.size() >= 3) {
size_t n = P.size();
adj2.resize(n - 2);
for (size_t i = 0; i < n - 2; ++i) {
adj2[i] = (get_edge_length(G, P[i], P[i + 2]) != INF);
}
}
vector<vector<pair<Vertex, int64_t>>> adj_R_reusable(G.N);
BoolVector in_R_reusable(G.N, false);
int32_t max_id = G.max_edge_id;
BoolVector in_C_edges_ws;
if (max_id != -1) {
in_C_edges_ws.resize(max_id + 1, false);
}
for (int parity_type = 0; parity_type < 2; ++parity_type) {
bool find_odd_S_sep = (parity_type == 0);
bool merge_even_P_indices = find_odd_S_sep;
DSU dsu(G.N);
if (P.size() >= 3) {
for (int32_t i = 0; i <= static_cast<int32_t>(P.size()) - 3; ++i) {
bool parity_match =
merge_even_P_indices ? (i % 2 == 0) : (i % 2 != 0);
if (parity_match && adj2[i]) {
dsu.unite(P[i], P[i + 2]);
}
}
}
for (Vertex u = 1; u < G.N; ++u) {
if (P_indices[u] != -1)
continue;
if (min_P_neighbor_index[u] == INF_INT)
continue;
int min_index = min_P_neighbor_index[u];
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
if (P_indices[v] != -1) {
int idx_v = P_indices[v];
bool parity_match = merge_even_P_indices ? (idx_v % 2 == 0)
: (idx_v % 2 != 0);
if (parity_match && idx_v > min_index) {
dsu.unite(u, v);
}
}
}
}
vector<int> deg_fat(G.N, 0);
for (const auto* edge_ptr : G.edge_list) {
Vertex u = edge_ptr->u, v = edge_ptr->v;
if (u >= G.N || v >= G.N || u == 0 || v == 0)
continue;
int fu = dsu.find(u), fv = dsu.find(v);
if (fu != fv) {
deg_fat[fu]++;
deg_fat[fv]++;
}
}
vector<int32_t> old_to_new_id(G.N, 0);
int32_t new_N = 1;
for (Vertex i = 1; i < G.N; ++i) {
if (deg_fat[i] > 0) {
old_to_new_id[i] = new_N++;
}
}
MultiGraph GMERGE(new_N);
for (Vertex i = 1; i < G.N; ++i) {
if (deg_fat[i] > 0) {
int32_t new_id = old_to_new_id[i];
if (new_id > 0 && new_id < new_N) {
GMERGE.adj[new_id].reserve(deg_fat[i]);
}
}
}
for (const auto* edge_ptr : G.edge_list) {
Vertex u = edge_ptr->u;
Vertex v = edge_ptr->v;
if (u >= G.N || v >= G.N || u == 0 || v == 0)
continue;
int fu = dsu.find(u);
int fv = dsu.find(v);
if (fu != fv) {
int32_t new_fu = old_to_new_id[fu];
int32_t new_fv = old_to_new_id[fv];
if (new_fu > 0 && new_fv > 0) {
int edge_id = edge_ptr->id;
GMERGE.adj[new_fu].push_back({new_fv, edge_id});
GMERGE.adj[new_fv].push_back({new_fu, edge_id});
}
}
}
BCCFinder_Multi bcc_finder(GMERGE);
bcc_finder.find_BCCs();
vector<Vertex> C_compact_vertices_vec;
BoolVector in_C_compact_vertices_ws(new_N, false);
for (const auto& C_edges : bcc_finder.BCC_edges) {
C_compact_vertices_vec.clear();
for (int32_t edge_id : C_edges) {
if (edge_id >= 0 && edge_id <= max_id)
in_C_edges_ws[edge_id] = true;
}
for (int32_t edge_id : C_edges) {
const OriginalEdge* edge_ptr = G.get_edge_ptr(edge_id);
if (!edge_ptr)
continue;
Vertex u = edge_ptr->u;
Vertex v = edge_ptr->v;
if (u >= G.N || v >= G.N || u == 0 || v == 0)
continue;
Vertex compact_u = old_to_new_id[dsu.find(u)];
Vertex compact_v = old_to_new_id[dsu.find(v)];
if (compact_u != V_NONE &&
!in_C_compact_vertices_ws[compact_u]) {
in_C_compact_vertices_ws[compact_u] = true;
C_compact_vertices_vec.push_back(compact_u);
}
if (compact_v != V_NONE &&
!in_C_compact_vertices_ws[compact_v]) {
in_C_compact_vertices_ws[compact_v] = true;
C_compact_vertices_vec.push_back(compact_v);
}
}
for (Vertex u_new : C_compact_vertices_vec) {
if (u_new > 0 && u_new < GMERGE.N) {
vector<const OriginalEdge*> R;
R.reserve(GMERGE.adj[u_new].size());
for (const auto& edge_info : GMERGE.adj[u_new]) {
int edge_id = edge_info.second;
if (edge_id >= 0 && edge_id <= max_id &&
in_C_edges_ws[edge_id]) {
R.push_back(G.get_edge_ptr(edge_id));
}
}
Path r = validate_separator(R, G, find_odd_S_sep, P_indices,
min_P_neighbor_index,
adj_R_reusable, in_R_reusable);
if (!r.empty()) {
X_result.push_back(std::move(r));
}
}
}
for (int32_t edge_id : C_edges) {
if (edge_id >= 0 && edge_id <= max_id)
in_C_edges_ws[edge_id] = false;
}
for (Vertex v : C_compact_vertices_vec) {
in_C_compact_vertices_ws[v] = false;
}
}
}
}
inline vector<Path> compute_X_ST(const Graph& G, const Path& P) {
vector<Path> X_ST_candidates;
compute_S_Separators(G, P, X_ST_candidates);
size_t X_S_size = X_ST_candidates.size();
Path P_rev = P;
reverse(P_rev.begin(), P_rev.end());
compute_S_Separators(G, P_rev, X_ST_candidates);
for (size_t i = X_S_size; i < X_ST_candidates.size(); ++i) {
reverse(X_ST_candidates[i].begin(), X_ST_candidates[i].end());
}
return X_ST_candidates;
}
inline vector<Path> compute_X_EXTRA(const Graph& G, const Path& P0) {
if (P0.empty())
return {};
vector<int64_t> P0_weights;
if (!P0.empty()) {
P0_weights.reserve(P0.size() - 1);
}
BoolVector is_edge_on_P0_vec;
bool use_vec = (G.max_edge_id != -1);
if (use_vec) {
is_edge_on_P0_vec.resize(G.max_edge_id + 1, false);
}
for (size_t i = 0; i < P0.size() - 1; ++i) {
Vertex u = P0[i], v = P0[i + 1];
pair<int64_t, int32_t> info = G.get_edge_info(u, v);
P0_weights.push_back(info.first);
int32_t id = info.second;
if (use_vec) {
if (id != -1 &&
id < static_cast<int32_t>(is_edge_on_P0_vec.size())) {
is_edge_on_P0_vec[id] = true;
} else if (id != -1) {
use_vec = false;
is_edge_on_P0_vec.clear();
is_edge_on_P0_vec.shrink_to_fit();
}
}
}
OptimizedSet<PackedKey> edges_P0_set;
if (!use_vec) {
edges_P0_set.reserve(P0.size() - 1);
for (size_t i = 0; i < P0.size() - 1; ++i) {
edges_P0_set.insert(edge_key(P0[i], P0[i + 1]));
}
}
vector<int32_t> component_id(G.N, 0);
int comp_count = 0;
queue<Vertex> q;
for (Vertex v = 1; v < G.N; ++v) {
if (component_id[v] == 0) {
comp_count++;
q.push(v);
component_id[v] = comp_count;
while (!q.empty()) {
Vertex u = q.front();
q.pop();
for (const auto& edge : G.adj[u]) {
Vertex neighbor = edge.to;
bool on_P0 = false;
if (use_vec) {
if (edge.id != -1 &&
edge.id < static_cast<int32_t>(
is_edge_on_P0_vec.size())) {
on_P0 = is_edge_on_P0_vec[edge.id];
}
} else {
on_P0 = edges_P0_set.count(edge_key(u, neighbor));
}
if (on_P0)
continue;
if (neighbor < G.N && component_id[neighbor] == 0) {
component_id[neighbor] = comp_count;
q.push(neighbor);
}
}
}
}
}
vector<int32_t> BEL(P0.size());
for (int32_t i = 0; i < static_cast<int32_t>(P0.size()); ++i) {
if (P0[i] < G.N)
BEL[i] = component_id[P0[i]];
}
vector<Path> X_EXTRA;
int32_t i = 0;
for (int32_t j = 1; j < static_cast<int32_t>(P0.size()); ++j) {
if (j > 1 && BEL[j] != BEL[j - 2]) {
if (i < j - 1) {
Path candidate;
vector<int64_t> candidate_weights;
for (int32_t k = i; k <= j - 1; ++k) {
candidate.push_back(P0[k]);
if (k < j - 1)
candidate_weights.push_back(P0_weights[k]);
}
if (candidate.size() >= 4 &&
is_useful_weighted(candidate, candidate_weights, G)) {
X_EXTRA.push_back(std::move(candidate));
}
}
i = j - 1;
}
if (j > 0 && BEL[j] == BEL[j - 1])
i = j;
}
if (i < static_cast<int32_t>(P0.size()) - 1) {
Path candidate;
vector<int64_t> candidate_weights;
for (int32_t k = i; k < static_cast<int32_t>(P0.size()); ++k) {
candidate.push_back(P0[k]);
if (k < static_cast<int32_t>(P0.size()) - 1)
candidate_weights.push_back(P0_weights[k]);
}
if (candidate.size() >= 4 &&
is_useful_weighted(candidate, candidate_weights, G)) {
X_EXTRA.push_back(std::move(candidate));
}
}
return X_EXTRA;
}
struct LR_Cache {
mutable FlatMap L_cache;
mutable FlatMap R_cache;
};
struct AVOID_precomputation {
const Graph& G;
const vector<Path>& X;
vector<int32_t> inner_r_id;
vector<int32_t> inner_idx;
vector<uint8_t> on_r_endpoint;
BoolVector is_edge_on_X;
vector<uint8_t> is_X_head_edge;
vector<vector<int32_t>> X_edge_ids;
BCCFinder bcc_finder;
vector<int32_t> head_rid_fwd;
vector<int32_t> head_rid_rev;
vector<Vertex> head_r2_fwd;
vector<Vertex> head_r2_rev;
LR_Cache lr_cache;
AVOID_precomputation(const Graph& graph, const vector<Path>& paths)
: G(graph), X(paths), bcc_finder(G) {
inner_r_id.assign(G.N, -1);
inner_idx.assign(G.N, -1);
on_r_endpoint.assign(G.N, 0);
int max_id = G.max_edge_id;
if (max_id != -1) {
is_edge_on_X.assign(max_id + 1, false);
is_X_head_edge.assign(max_id + 1, 0);
head_rid_fwd.assign(max_id + 1, -1);
head_rid_rev.assign(max_id + 1, -1);
head_r2_fwd.assign(max_id + 1, V_NONE);
head_r2_rev.assign(max_id + 1, V_NONE);
}
X_edge_ids.resize(X.size());
size_t total_edges_X = 0;
for (int32_t r_id = 0; r_id < static_cast<int32_t>(X.size()); ++r_id) {
const Path& r = X[r_id];
if (r.empty())
continue;
if (r.size() > 1) {
X_edge_ids[r_id].reserve(r.size() - 1);
total_edges_X += r.size() - 1;
}
if (r.front() < G.N)
on_r_endpoint[r.front()] |= 1;
if (r.back() < G.N)
on_r_endpoint[r.back()] |= 2;
for (size_t i = 1; i < r.size() - 1; ++i) {
if (r[i] < G.N) {
inner_r_id[r[i]] = r_id;
inner_idx[r[i]] = i;
}
}
for (size_t i = 0; i < r.size() - 1; ++i) {
int32_t edge_id = get_edge_id(G, r[i], r[i + 1]);
X_edge_ids[r_id].push_back(edge_id);
if (edge_id != -1 &&
edge_id < static_cast<int32_t>(is_edge_on_X.size())) {
is_edge_on_X[edge_id] = true;
if (i == 0) {
if (r[i] < r[i + 1])
is_X_head_edge[edge_id] |= 1;
else
is_X_head_edge[edge_id] |= 2;
}
}
}
if (r.size() >= 3 && max_id != -1) {
const auto& r_eids = X_edge_ids[r_id];
int eid0 = r_eids[0];
if (eid0 != -1 && eid0 <= max_id) {
if (r[0] < r[1]) {
head_rid_fwd[eid0] = r_id;
head_r2_fwd[eid0] = r[2];
} else {
head_rid_rev[eid0] = r_id;
head_r2_rev[eid0] = r[2];
}
}
int eidL = r_eids.back();
if (eidL != -1 && eidL <= max_id) {
if (r[r.size() - 2] < r[r.size() - 1]) {
head_rid_rev[eidL] = r_id;
head_r2_rev[eidL] = r[r.size() - 3];
} else {
head_rid_fwd[eidL] = r_id;
head_r2_fwd[eidL] = r[r.size() - 3];
}
}
}
}
lr_cache.L_cache.init(total_edges_X * 2);
lr_cache.R_cache.init(total_edges_X * 2);
bcc_finder.forbidden_edge_ids = &is_edge_on_X;
bcc_finder.find_BCCs();
}
inline bool is_inner(Vertex u) const {
return u > 0 && u < G.N && inner_r_id[u] != -1;
}
inline int32_t get_r_id(Vertex u) const {
return (u > 0 && u < G.N) ? inner_r_id[u] : -1;
}
inline int32_t get_idx_in_r(Vertex u) const {
return (u > 0 && u < G.N) ? inner_idx[u] : -1;
}
inline bool is_on_r(Vertex node, int32_t r_id) const {
if (r_id < 0 || r_id >= static_cast<int32_t>(X.size()))
return false;
if (is_inner(node) && get_r_id(node) == r_id)
return true;
const Path& r = X[r_id];
return !r.empty() && (node == r.front() || node == r.back());
}
inline bool edge_on_X(int32_t edge_id) const {
return edge_id != -1 &&
edge_id < static_cast<int32_t>(is_edge_on_X.size()) &&
is_edge_on_X[edge_id];
}
inline bool X_head(Vertex u, Vertex v, int32_t edge_id) const {
if (edge_id != -1 &&
edge_id < static_cast<int32_t>(is_X_head_edge.size())) {
if (u < v) {
return (is_X_head_edge[edge_id] & 1) != 0;
} else {
return (is_X_head_edge[edge_id] & 2) != 0;
}
}
return false;
}
inline bool check_strong_connectivity(Vertex ri, Vertex u,
int32_t edge_id_ri_u,
Vertex target_v) const {
bool edge_in_G_prime = !edge_on_X(edge_id_ri_u);
if (edge_in_G_prime) {
if (edge_id_ri_u != -1 &&
edge_id_ri_u <
static_cast<int32_t>(bcc_finder.edge_to_BCC.size())) {
int32_t bcc_idx = bcc_finder.edge_to_BCC[edge_id_ri_u];
if (bcc_idx != -1 && bcc_finder.is_in_BCC(bcc_idx, target_v)) {
return true;
}
}
} else {
int32_t r_prime_id = -1;
Vertex r_prime_2 = V_NONE;
if (edge_id_ri_u != -1 &&
edge_id_ri_u < static_cast<int32_t>(head_rid_fwd.size())) {
if (ri < u) {
r_prime_id = head_rid_fwd[edge_id_ri_u];
r_prime_2 = head_r2_fwd[edge_id_ri_u];
} else {
r_prime_id = head_rid_rev[edge_id_ri_u];
r_prime_2 = head_r2_rev[edge_id_ri_u];
}
}
if (r_prime_id != -1 && r_prime_2 != V_NONE) {
int32_t r_id = get_r_id(ri);
if (r_id == -1)
return false;
bool r_prime_2_on_r = is_on_r(r_prime_2, r_id);
if (r_prime_2_on_r) {
if (r_prime_2 == target_v) {
return true;
}
} else {
int32_t chord_edge_id = get_edge_id(G, r_prime_2, ri);
if (chord_edge_id != -1 &&
chord_edge_id < static_cast<int32_t>(
bcc_finder.edge_to_BCC.size())) {
int32_t bcc_idx = bcc_finder.edge_to_BCC[chord_edge_id];
if (bcc_idx != -1 &&
bcc_finder.is_in_BCC(bcc_idx, target_v)) {
return true;
}
}
}
}
}
return false;
}
inline Vertex get_L(int32_t r_id, Vertex u) const {
if (r_id < 0 || r_id >= (int32_t)X.size() || u <= 0 || u >= G.N)
return V_NONE;
PackedKey key = lr_key(r_id, u);
Vertex cached;
if (lr_cache.L_cache.try_get(key, cached))
return cached;
const Path& r = X[r_id];
Vertex L_val = V_NONE;
for (int32_t i = 1; i < (int32_t)r.size() - 1; ++i) {
Vertex ri = r[i];
int32_t eid = G.get_edge_info(ri, u).second;
if (eid != -1) {
L_val = ri;
if (i >= 2) {
Vertex ri_minus_2 = r[i - 2];
if (check_strong_connectivity(ri, u, eid, ri_minus_2)) {
L_val = ri_minus_2;
}
}
break;
}
}
lr_cache.L_cache.set(key, L_val);
return L_val;
}
inline Vertex get_R(int32_t r_id, Vertex u) const {
if (r_id < 0 || r_id >= (int32_t)X.size() || u <= 0 || u >= G.N)
return V_NONE;
PackedKey key = lr_key(r_id, u);
Vertex cached;
if (lr_cache.R_cache.try_get(key, cached))
return cached;
const Path& r = X[r_id];
Vertex R_val = V_NONE;
int32_t Max_R_idx = -1;
for (int32_t i = 1; i < (int32_t)r.size() - 1; ++i) {
Vertex ri = r[i];
int32_t eid = G.get_edge_info(ri, u).second;
if (eid != -1) {
Vertex Current_R_val = ri;
int32_t Current_R_idx = i;
if (i <= (int32_t)r.size() - 3) {
Vertex ri_plus_2 = r[i + 2];
if (check_strong_connectivity(ri, u, eid, ri_plus_2)) {
Current_R_val = ri_plus_2;
Current_R_idx = i + 2;
}
}
if (Current_R_idx > Max_R_idx) {
Max_R_idx = Current_R_idx;
R_val = Current_R_val;
}
}
}
lr_cache.R_cache.set(key, R_val);
return R_val;
}
};
inline Path AVOID(const Graph& G, Vertex S, Vertex T, const vector<Path>& X,
const BoolVector& is_bad) {
AVOID_precomputation pre(G, X);
using G1Node = pair<Vertex, int>;
G1Node StartNode = {S, 0};
G1Node EndNode = {T, 0};
vector<array<int64_t, 2>> dist(G.N, {INF, INF});
G1Node InvalidParent = {V_NONE, 0};
vector<array<G1Node, 2>> parent(G.N, {InvalidParent, InvalidParent});
RadixHeap64<uint64_t, G1Node> pq;
if (S >= G.N || T >= G.N || S == 0 || T == 0)
return {};
if (!is_bad.empty() && S < static_cast<int32_t>(is_bad.size()) && is_bad[S])
return {};
dist[S][0] = 0;
pq.push(0, StartNode);
int64_t shortest_dist = INF;
while (!pq.empty()) {
auto [d_unsigned, u_node] = pq.top();
pq.pop();
int64_t d = (int64_t)d_unsigned;
Vertex u = u_node.first;
int32_t state_u = u_node.second;
if (d != dist[u][state_u])
continue;
if (u_node == EndNode) {
shortest_dist = d;
break;
}
int32_t r_id_u = -1;
const Path* r_u_ptr = nullptr;
int32_t idx_u = -1;
if (state_u == 1) {
if (!pre.is_inner(u))
continue;
r_id_u = pre.get_r_id(u);
if (r_id_u != -1) {
r_u_ptr = &X[r_id_u];
idx_u = pre.get_idx_in_r(u);
}
}
for (const auto& edge : G.adj[u]) {
Vertex v = edge.to;
int64_t w = edge.weight;
int32_t edge_id = edge.id;
if (!is_bad.empty() && v < static_cast<int32_t>(is_bad.size()) &&
is_bad[v])
continue;
bool v_is_inner = pre.is_inner(v);
auto try_transition = [&](int32_t state_v) {
int64_t new_dist = d + w;
if (new_dist < dist[v][state_v]) {
dist[v][state_v] = new_dist;
parent[v][state_v] = G1Node{u, state_u};
pq.push((uint64_t)new_dist, G1Node{v, state_v});
}
};
if (state_u == 0) {
bool transition_to_high = false;
if (v_is_inner) {
int32_t r_id_v = pre.get_r_id(v);
const Path& r_v = X[r_id_v];
int32_t idx_v = pre.get_idx_in_r(v);
bool is_head_entry =
(r_v.size() > 1 && u == r_v[0] && v == r_v[1]);
bool is_special_case_entry =
(!pre.is_on_r(u, r_id_v) &&
idx_v == static_cast<int32_t>(r_v.size()) - 3 &&
pre.get_L(r_id_v, u) == v);
if (is_head_entry || is_special_case_entry) {
transition_to_high = true;
}
}
if (transition_to_high) {
try_transition(1);
}
bool transition_to_low = true;
if (pre.X_head(u, v, edge_id)) {
transition_to_low = false;
}
if (v_is_inner && transition_to_low) {
int32_t r_id_v = pre.get_r_id(v);
if (!pre.is_on_r(u, r_id_v) && pre.get_L(r_id_v, u) == v) {
transition_to_low = false;
}
}
if (transition_to_low) {
try_transition(0);
}
} else {
if (r_u_ptr == nullptr)
continue;
const Path& r_u = *r_u_ptr;
if (v_is_inner) {
bool transition_high_high = true;
int32_t r_id_v = pre.get_r_id(v);
if (r_id_u == r_id_v) {
if (idx_u >= 1 && v == r_u[idx_u - 1])
transition_high_high = false;
if (idx_u >= 2 && v == r_u[idx_u - 2])
transition_high_high = false;
} else {
if (!pre.is_on_r(v, r_id_u) &&
pre.get_R(r_id_u, v) == u)
transition_high_high = false;
}
if (transition_high_high) {
try_transition(1);
}
}
bool transition_high_low = true;
if (pre.edge_on_X(edge_id))
transition_high_low = false;
if (idx_u >= 2 && v == r_u[idx_u - 2])
transition_high_low = false;
if (!pre.is_on_r(v, r_id_u) && pre.get_R(r_id_u, v) == u)
transition_high_low = false;
if (v_is_inner) {
int32_t r_id_v = pre.get_r_id(v);
if (r_id_u != r_id_v && !pre.is_on_r(u, r_id_v) &&
pre.get_L(r_id_v, u) == v)
transition_high_low = false;
}
if (transition_high_low) {
try_transition(0);
}
}
}
}
if (shortest_dist == INF)
return {};
Path path_G;
G1Node curr = EndNode;
while (curr != StartNode) {
path_G.push_back(curr.first);
G1Node p = parent[curr.first][curr.second];
if (p.first == V_NONE)
break;
curr = p;
}
if (curr == StartNode)
path_G.push_back(StartNode.first);
else
return {};
reverse(path_G.begin(), path_G.end());
return path_G;
}
inline Path ShortestNonSeparatingPath(const Graph& G_input, Vertex S_original,
Vertex T_original) {
if (S_original == T_original)
return {S_original};
BridgeFinder bf(G_input);
bf.find_Bridges();
vector<int32_t> component_id(G_input.N, 0);
int32_t comp_count = 0;
vector<Vertex> stack;
if (G_input.N > 1)
stack.reserve(G_input.N);
for (Vertex v = 1; v < G_input.N; ++v) {
if (component_id[v] == 0) {
comp_count++;
stack.push_back(v);
component_id[v] = comp_count;
while (!stack.empty()) {
Vertex u = stack.back();
stack.pop_back();
for (const auto& edge : G_input.adj[u]) {
if (edge.id != -1 &&
edge.id < static_cast<int32_t>(bf.is_bridge.size()) &&
bf.is_bridge[edge.id])
continue;
Vertex neighbor = edge.to;
if (neighbor < G_input.N && component_id[neighbor] == 0) {
component_id[neighbor] = comp_count;
stack.push_back(neighbor);
}
}
}
}
}
if (S_original >= G_input.N || T_original >= G_input.N || S_original == 0 ||
T_original == 0 ||
component_id[S_original] != component_id[T_original] ||
component_id[S_original] == 0) {
return {};
}
int32_t target_comp = component_id[S_original];
vector<Vertex> old_to_new_v(G_input.N, V_NONE);
vector<Vertex> new_to_old_v;
new_to_old_v.reserve(G_input.N);
new_to_old_v.push_back(V_NONE);
Vertex new_N_counter = 1;
for (Vertex v = 1; v < G_input.N; ++v) {
if (component_id[v] == target_comp) {
old_to_new_v[v] = new_N_counter++;
new_to_old_v.push_back(v);
}
}
int32_t N_prime_count = new_N_counter - 1;
int32_t M_prime_count = 0;
vector<int32_t> degrees(N_prime_count + 1, 0);
for (const auto* ptr : G_input.edge_list) {
if (ptr->u < G_input.N && component_id[ptr->u] == target_comp &&
ptr->v < G_input.N && component_id[ptr->v] == target_comp) {
M_prime_count++;
Vertex u_prime = old_to_new_v[ptr->u];
Vertex v_prime = old_to_new_v[ptr->v];
if (u_prime != V_NONE)
degrees[u_prime]++;
if (v_prime != V_NONE)
degrees[v_prime]++;
}
}
Graph G_prime(N_prime_count, M_prime_count);
Vertex S_prime = old_to_new_v[S_original];
Vertex T_prime = old_to_new_v[T_original];
for (int32_t i = 1; i <= N_prime_count; ++i) {
G_prime.adj[i].reserve(degrees[i]);
}
int32_t new_edge_id = 0;
for (const auto* ptr : G_input.edge_list) {
if (ptr->u < G_input.N && component_id[ptr->u] == target_comp &&
ptr->v < G_input.N && component_id[ptr->v] == target_comp) {
Vertex u_prime = old_to_new_v[ptr->u];
Vertex v_prime = old_to_new_v[ptr->v];
G_prime.add_edge(u_prime, v_prime, ptr->weight, new_edge_id++,
nullptr);
}
}
G_prime.finalize_construction();
const Graph& G = G_prime;
Vertex S = S_prime;
Vertex T = T_prime;
BoolVector is_bad = compute_BAD_G(G, S, T);
pair<int64_t, Path> result_P = dijkstra(G, S, T, is_bad);
if (result_P.first == INF)
return {};
Path P = result_P.second;
vector<Path> X_ST = compute_X_ST(G, P);
vector<int32_t> P_indices = get_P_indices_vec(P, G.N);
vector<int32_t> forbidden_ids_vec;
int32_t max_id = -1;
auto find_edge_id = [&](Vertex u, Vertex v) {
return get_edge_id(G, u, v);
};
for (const Path& r : X_ST) {
if (r.size() < 4)
continue;
bool is_S_sep = true;
for (size_t i = 2; i < r.size(); ++i) {
if (r[i] >= G.N || P_indices[r[i]] == -1) {
is_S_sep = false;
break;
}
}
bool is_T_sep = true;
for (size_t i = 0; i <= r.size() - 3; ++i) {
if (r[i] >= G.N || P_indices[r[i]] == -1) {
is_T_sep = false;
break;
}
}
if (is_S_sep) {
int32_t id = find_edge_id(r[r.size() - 2], r[r.size() - 1]);
if (id != -1) {
forbidden_ids_vec.push_back(id);
if (id > max_id)
max_id = id;
}
}
if (is_T_sep) {
int32_t id = find_edge_id(r[0], r[1]);
if (id != -1) {
forbidden_ids_vec.push_back(id);
if (id > max_id)
max_id = id;
}
}
}
BoolVector G0_forbidden_edge_ids;
if (max_id != -1) {
G0_forbidden_edge_ids.resize(max_id + 1, false);
for (int32_t id : forbidden_ids_vec)
G0_forbidden_edge_ids[id] = true;
}
pair<int64_t, Path> result_P0 =
dijkstra(G, S, T, is_bad, G0_forbidden_edge_ids);
Path P0;
if (result_P0.first != INF)
P0 = result_P0.second;
vector<Path> X_EXTRA = compute_X_EXTRA(G, P0);
vector<Path> X_combined = std::move(X_ST);
X_combined.reserve(X_combined.size() + X_EXTRA.size());
X_combined.insert(X_combined.end(),
std::make_move_iterator(X_EXTRA.begin()),
std::make_move_iterator(X_EXTRA.end()));
std::sort(X_combined.begin(), X_combined.end());
X_combined.erase(std::unique(X_combined.begin(), X_combined.end()),
X_combined.end());
const vector<Path>& X = X_combined;
Path result_path_prime = AVOID(G, S, T, X, is_bad);
if (result_path_prime.empty()) {
return {};
}
Path result_path_original;
result_path_original.reserve(result_path_prime.size());
for (Vertex v_prime : result_path_prime) {
if (v_prime > 0 &&
v_prime < static_cast<int32_t>(new_to_old_v.size())) {
result_path_original.push_back(new_to_old_v[v_prime]);
} else {
return {};
}
}
return result_path_original;
}
constexpr int __buffsize = 1 << 20;
char __buff[__buffsize];
char *__buffs = __buff, *__buffe = __buff;
inline char getc() {
if (__buffs == __buffe) {
size_t flywheel = fread(__buff, 1, __buffsize, stdin);
if (flywheel == 0)
return EOF;
__buffe = __buff + flywheel;
__buffs = __buff;
}
return *(__buffs++);
}
template <typename T> inline void read_number(T& x) {
x = 0;
static char c;
bool flag = false;
while ((c = getc()) != EOF && (c < '0' || c > '9') && c != '-')
;
if (c == EOF)
return;
if (c == '-') {
flag = true;
c = getc();
} else if (c >= '0' && c <= '9') {
x = c - '0';
c = getc();
}
while (c != EOF && c >= '0' && c <= '9') {
x = (x << 3) + (x << 1) + (c - '0');
c = getc();
}
if (flag)
x = -x;
}
inline void read_int(int32_t& x) { read_number<int32_t>(x); }
inline void read_long(int64_t& x) { read_number<int64_t>(x); }
int main() {
ios_base::sync_with_stdio(false);
int32_t n, m;
read_int(n);
read_int(m);
struct InputEdge {
PackedKey key;
int64_t w;
bool operator<(const InputEdge& other) const {
if (key != other.key)
return key < other.key;
return w < other.w;
}
};
vector<InputEdge> input_edges;
if (m > 0)
input_edges.reserve(m);
for (int32_t i = 0; i < m; ++i) {
int32_t u, v;
int64_t w;
read_int(u);
read_int(v);
read_long(w);
if (u != v) {
PackedKey key = edge_key(u, v);
input_edges.push_back({key, w});
}
}
sort(input_edges.begin(), input_edges.end());
int32_t s, t;
read_int(s);
read_int(t);
int32_t unique_edge_count = 0;
vector<int32_t> degrees(n + 1, 0);
if (!input_edges.empty()) {
unique_edge_count = 1;
auto count_degree = [&](const InputEdge& edge) {
pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
if (uv.first <= n)
degrees[uv.first]++;
if (uv.second <= n)
degrees[uv.second]++;
};
count_degree(input_edges[0]);
for (size_t i = 1; i < input_edges.size(); ++i) {
if (input_edges[i].key != input_edges[i - 1].key) {
unique_edge_count++;
count_degree(input_edges[i]);
}
}
}
Graph G(n, unique_edge_count);
for (int32_t i = 1; i <= n && i < G.N; ++i) {
G.adj[i].reserve(degrees[i]);
}
int32_t edge_id_counter = 0;
if (!input_edges.empty()) {
auto add_edge_to_G = [&](const InputEdge& edge) {
pair<Vertex, Vertex> uv = unpack_edge_key(edge.key);
int64_t w = edge.w;
int32_t id = edge_id_counter++;
G.add_edge(uv.first, uv.second, w, id, nullptr);
};
add_edge_to_G(input_edges[0]);
for (size_t i = 1; i < input_edges.size(); ++i) {
if (input_edges[i].key != input_edges[i - 1].key) {
add_edge_to_G(input_edges[i]);
}
}
}
G.finalize_construction();
Path result = ShortestNonSeparatingPath(G, s, t);
if (result.empty()) {
printf("-1\n");
} else {
int64_t total_weight = 0;
for (size_t i = 0; i < result.size() - 1; ++i) {
total_weight += get_edge_length(G, result[i], result[i + 1]);
}
printf("%lld\n", (long long)total_weight);
}
return 0;
}
回复
共 0 条回复，欢迎继续交流。
正在加载回复...