結果
| 問題 |
No.1326 ふたりのDominator
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:48 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 13,625 bytes |
| コンパイル時間 | 703 ms |
| コンパイル使用メモリ | 75,628 KB |
| 実行使用メモリ | 33,672 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:37 |
| 合計ジャッジ時間 | 3,918 ms |
|
ジャッジサーバーID （参考情報） |
judge4 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 1 |
| other | AC * 15 WA * 9 |
コンパイルメッセージ
main.cpp: In function ‘int main()’:
main.cpp:216:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
216 | scanf("%d %d", &N, &M);
| ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:219:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
219 | scanf("%d %d", &u, &v);
| ~~~~~^~~~~~~~~~~~~~~~~
main.cpp:272:10: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
272 | scanf("%d", &Q); // Read number of queries
| ~~~~~^~~~~~~~~~
main.cpp:275:14: warning: ignoring return value of ‘int scanf(const char*, ...)’ declared with attribute ‘warn_unused_result’ [-Wunused-result]
275 | scanf("%d %d", &x, &y); // Read query pair (x, y)
| ~~~~~^~~~~~~~~~~~~~~~~
ソースコード
#include <vector>
#include <stack>
#include <algorithm>
#include <set>
#include <cstdio>
#include <vector> // Make sure vector is included
using namespace std;
// Constants and global variables
const int MAXN = 50005; // Maximum number of vertices
const int MAXM = 100005; // Maximum number of edges
// Maximum possible nodes in block-cut tree (N vertices + M blocks worst case)
// Increased size slightly for safety buffer (+5)
const int MAX_TREE_NODES = MAXN + MAXM + 5;
vector<int> adj[MAXN + 1]; // Original graph adjacency list (1-based indexing)
int N, M; // Number of vertices and edges
int dfn[MAXN + 1], low[MAXN + 1], timer; // Discovery time and low-link value for Tarjan's
stack<pair<int, int>> st; // Stack to store edges for identifying BCCs
bool is_articulation[MAXN + 1]; // Flags if a vertex is an articulation point
vector<int> tree_adj[MAX_TREE_NODES]; // Block-cut tree adjacency list
// Maps original vertex ID to its corresponding node ID in the block-cut tree.
// If vertex `u` is an AP, its ID is `u`. Otherwise, it's the ID of the block it belongs to.
int tree_node_id[MAXN + 1];
// Flags if a node in the block-cut tree corresponds to an articulation point (C-node)
bool is_C_node[MAX_TREE_NODES];
int block_cnt = 0; // Counter for blocks (BCCs) found
/**
* @brief Tarjan's algorithm to find articulation points and build the Block-Cut Tree.
* Finds BiConnected Components (BCCs) and constructs the tree where nodes represent
* articulation points (C-nodes) and BCCs (B-nodes).
*
* @param u Current vertex being visited.
* @param p Parent of u in DFS tree (-1 if root).
*/
void find_bccs_and_build_tree_tarjan(int u, int p = -1) {
dfn[u] = low[u] = ++timer;
int children = 0; // Count children in DFS tree for root AP check
for (int v : adj[u]) {
if (v == p) continue; // Skip edge back to parent
if (dfn[v] > 0) { // If v is already visited
low[u] = min(low[u], dfn[v]); // Update low[u] using back edge
if (dfn[v] < dfn[u]) { // If it's a back edge to an ancestor
st.push({u, v}); // Push edge onto stack
}
} else { // If v is not visited
children++;
st.push({u, v}); // Push edge onto stack before exploring v
find_bccs_and_build_tree_tarjan(v, u); // Recursive DFS call
low[u] = min(low[u], low[v]); // Update low[u] based on child's low-link value
// Check if u is an articulation point based on child v
if ((p != -1 && low[v] >= dfn[u]) || (p == -1 && children > 1)) {
if (!is_articulation[u]) { // Mark only once and assign properties
is_articulation[u] = true;
tree_node_id[u] = u; // AP node ID is its vertex ID
is_C_node[u] = true; // Mark it as a C-node
}
}
// If low[v] >= dfn[u], it indicates that the component involving edge (u,v)
// and the subtree rooted at v forms a BCC.
if (low[v] >= dfn[u]) {
block_cnt++;
int block_node_id = N + block_cnt; // Assign a new ID for this block node
is_C_node[block_node_id] = false; // It's a B-node
set<int> bcc_vertices; // Store vertices in this BCC to avoid duplicates
pair<int, int> edge;
// Pop edges from stack until edge (u,v) is popped. These edges form the BCC.
do {
if (st.empty()) break; // Safety check
edge = st.top();
st.pop();
bcc_vertices.insert(edge.first);
bcc_vertices.insert(edge.second);
} while (!((edge.first == u && edge.second == v) || (edge.first == v && edge.second == u))); // Check both directions for edge {u,v}
// Add edges in the block-cut tree between the block node and APs within the BCC.
// Map non-AP vertices to the block node ID.
for (int node : bcc_vertices) {
if (is_articulation[node]) {
// Connect AP node `node` and block node `block_node_id`
tree_adj[node].push_back(block_node_id);
tree_adj[block_node_id].push_back(node);
is_C_node[node] = true; // Ensure AP is marked as C-node
} else {
// Non-AP vertices belong to exactly one block. Map them if not already mapped.
if(tree_node_id[node] == 0) {
tree_node_id[node] = block_node_id;
}
}
}
}
}
}
}
// LCA related structures and functions
int depth[MAX_TREE_NODES]; // Depth of each node in the block-cut tree
int parent[MAX_TREE_NODES][20]; // Binary lifting table for LCA: parent[i][j] is 2^j-th ancestor of i
// Stores the count of C-nodes on the path from the root to node i
int path_C_count[MAX_TREE_NODES];
/**
* @brief Performs DFS on the block-cut tree to compute depths, parents for LCA,
* and prefix sums of C-nodes count along paths from the root.
* @param u Current node ID in BCT.
* @param p Parent node ID in BCT DFS tree (-1 for root).
* @param d Current depth.
*/
void dfs_lca(int u, int p, int d) {
depth[u] = d;
parent[u][0] = p;
path_C_count[u] = (is_C_node[u] ? 1 : 0); // Add 1 if current node is C-node
if(p != -1) {
// Index check for safety, although p should always be valid if called correctly
if (p >= 1 && p < MAX_TREE_NODES) {
path_C_count[u] += path_C_count[p]; // Add parent's path count
}
}
// Precompute ancestors for binary lifting
for (int i = 1; i < 20; ++i) {
if (parent[u][i-1] != -1) {
parent[u][i] = parent[parent[u][i-1]][i-1]; // 2^i ancestor is 2^(i-1) ancestor of 2^(i-1) ancestor
} else {
parent[u][i] = -1; // No ancestor at this level
}
}
// Recurse for children
for (int v : tree_adj[u]) {
if (v != p) { // Avoid going back up to parent
dfs_lca(v, u, d + 1);
}
}
}
/**
* @brief Computes the Lowest Common Ancestor (LCA) of two nodes in the block-cut tree using binary lifting.
* @param u First node ID.
* @param v Second node ID.
* @return The node ID of the LCA of u and v, or -1 if invalid input or nodes are in different components.
*/
int lca(int u, int v) {
// Basic validity checks
if (u <= 0 || v <= 0 || u >= MAX_TREE_NODES || v >= MAX_TREE_NODES || depth[u] == -1 || depth[v] == -1) return -1;
// Ensure u is the deeper node
if (depth[u] < depth[v]) swap(u, v);
// Lift node u up until it's at the same depth as v
for (int i = 19; i >= 0; --i) {
if (parent[u][i] != -1 && depth[parent[u][i]] >= depth[v]) {
u = parent[u][i];
}
}
// If u and v are now the same node, it's the LCA
if (u == v) return u;
// Lift u and v up together maintaining the property that their parents are different
// until their parents become the same.
for (int i = 19; i >= 0; --i) {
if (parent[u][i] != -1 && parent[v][i] != -1 && parent[u][i] != parent[v][i]) {
u = parent[u][i];
v = parent[v][i];
}
}
// The parent of u (and v) is now the LCA
return parent[u][0];
}
/**
* @brief Initializes data structures required for LCA queries.
* It computes depths, parent pointers, and path C-node counts for all nodes in the BCT.
*/
void initialize_lca() {
int max_node_id = N + block_cnt; // Maximum node ID used in the BCT
// Initialize depth to -1 to mark nodes as unvisited by LCA DFS
fill(depth, depth + max_node_id + 1, -1);
// Initialize parent table with -1
for (int i = 1; i <= max_node_id; ++i) {
for (int j = 0; j < 20; ++j) {
parent[i][j] = -1;
}
}
// Since the original graph is connected, the block-cut tree is connected.
// We can start DFS from any valid node to cover the entire tree.
for (int i = 1; i <= max_node_id; ++i) {
bool node_exists = false; // Check if node 'i' actually exists in our construction
if (i <= N) { // If ID corresponds to an original vertex
if (is_articulation[i]) node_exists = true; // APs retain their ID
else if(tree_node_id[i] != 0) node_exists = true; // Non-APs are mapped to a block ID
} else { // If ID corresponds to a block node
if (i <= N + block_cnt) node_exists = true; // Check if block ID is valid
}
// If node exists and hasn't been visited by LCA DFS yet, start DFS from here
if (node_exists && depth[i] == -1) {
dfs_lca(i, -1, 0); // Start DFS from node 'i' with parent -1 and depth 0
}
}
}
int main() {
scanf("%d %d", &N, &M);
for (int i = 0; i < M; ++i) {
int u, v;
scanf("%d %d", &u, &v);
adj[u].push_back(v);
adj[v].push_back(u);
}
// Initialize Tarjan's algorithm related arrays
timer = 0;
fill(dfn + 1, dfn + N + 1, 0);
fill(low + 1, low + N + 1, 0);
fill(is_articulation + 1, is_articulation + N + 1, false);
fill(tree_node_id + 1, tree_node_id + N + 1, 0);
fill(is_C_node, is_C_node + MAX_TREE_NODES, false); // Initialize is_C_node for all potential node IDs
// Run Tarjan's algorithm starting from each unvisited vertex
// This handles potentially disconnected graphs, though problem states graph is connected.
for(int i=1; i<=N; ++i) {
if(dfn[i] == 0) { // If vertex i not yet visited
find_bccs_and_build_tree_tarjan(i);
// After the main DFS call for a component returns, check if stack has remaining edges.
// This handles the case where the entire component (or the part containing the root) is a single BCC.
if (!st.empty()) {
block_cnt++;
int block_node_id = N + block_cnt;
is_C_node[block_node_id] = false; // Last block node
set<int> bcc_vertices;
while(!st.empty()) {
pair<int, int> edge = st.top(); st.pop();
bcc_vertices.insert(edge.first);
bcc_vertices.insert(edge.second);
}
// Connect the last block node correctly
for (int node : bcc_vertices) {
if (is_articulation[node]) {
tree_adj[node].push_back(block_node_id);
tree_adj[block_node_id].push_back(node);
is_C_node[node] = true; // Ensure AP marked as C-node
} else {
// Map non-AP node if not already mapped
if(tree_node_id[node] == 0) {
tree_node_id[node] = block_node_id;
}
}
}
}
}
}
// Initialize LCA data structures after building the block-cut tree
initialize_lca();
int Q;
scanf("%d", &Q); // Read number of queries
while (Q--) {
int x, y;
scanf("%d %d", &x, &y); // Read query pair (x, y)
if (x == y) { // If x and y are the same vertex
printf("0\n"); // Removing any other vertex z cannot disconnect x from itself
continue;
}
// Get corresponding node IDs in the block-cut tree
// If vertex is AP, its ID is vertex ID itself. Otherwise, use mapped block ID.
int tx = (is_articulation[x] ? x : tree_node_id[x]);
int ty = (is_articulation[y] ? y : tree_node_id[y]);
// Basic check if nodes were successfully mapped. Should not fail for connected graph N>=3.
if (tx == 0 || ty == 0) {
printf("0\n"); // Indicates an issue or edge case not handled
continue;
}
// If x and y map to the same node in BCT, they are in the same block.
// Removing any single vertex z != x, y cannot disconnect them.
if (tx == ty) {
printf("0\n");
continue;
}
// Find the LCA of tx and ty in the block-cut tree
int ancestor = lca(tx, ty);
if (ancestor == -1) { // If LCA is -1, indicates an error (e.g., disconnected tree, invalid nodes)
printf("0\n");
continue;
}
// Calculate the number of C-nodes (APs) on the path between tx and ty using path counts
// Count(tx to root) + Count(ty to root) - 2 * Count(LCA to root)
int count = path_C_count[tx] + path_C_count[ty] - 2 * path_C_count[ancestor];
// If the LCA itself is a C-node, it was counted in both paths and subtracted twice. Add it back once.
if (is_C_node[ancestor]) {
count++;
}
// We need to count vertices z such that z != x and z != y.
// The path count includes all C-nodes on the path. If x or y are APs,
// their corresponding C-nodes are endpoints of the path tx -- ty.
// We must subtract them from the count.
if (is_articulation[x]) {
count--;
}
if (is_articulation[y]) {
count--;
}
// The final count must be non-negative.
printf("%d\n", max(0, count));
}
return 0;
}