結果
| 問題 | No.1983 [Cherry 4th Tune C] 南の島のマーメイド |
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:11:34 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,110 bytes |
| コンパイル時間 | 1,266 ms |
| コンパイル使用メモリ | 110,680 KB |
| 実行使用メモリ | 43,864 KB |
| 最終ジャッジ日時 | 2025-05-14 13:13:37 |
| 合計ジャッジ時間 | 8,250 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| other | AC * 16 WA * 25 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <functional> // Required for std::function
// Disjoint Set Union (DSU) structure with Path Compression and Union by Size optimizations
struct DSU {
std::vector<int> parent; // Stores the parent of each element
std::vector<int> sz; // Stores the size of the component (subtree size in the DSU tree) rooted at i
// Constructor initializes DSU for n elements, indexed 1 to n
DSU(int n) {
parent.resize(n + 1);
// Initialize each element as its own parent (representing n distinct sets)
// Vertices are 1-based, so we initialize from index 1 to n
std::iota(parent.begin() + 1, parent.end(), 1);
// Initialize the size of each set to 1
sz.assign(n + 1, 1);
}
// Finds the representative (root) of the set containing x, using path compression
int find(int x) {
// If x is the root of its set, return x
if (parent[x] == x) {
return x;
}
// Path compression: recursively find the root and make x point directly to it
return parent[x] = find(parent[x]);
}
// Unites the sets containing x and y, using union by size heuristic
void unite(int x, int y) {
int rootX = find(x); // Find the root of the set containing x
int rootY = find(y); // Find the root of the set containing y
// If x and y are already in the same set, do nothing
if (rootX != rootY) {
// Union by size: attach the smaller tree to the root of the larger tree
// This helps keep the DSU tree relatively flat, optimizing 'find' operations
if (sz[rootX] < sz[rootY]) {
std::swap(rootX, rootY); // Ensure rootX represents the larger tree
}
parent[rootY] = rootX; // Make rootX the parent of rootY
sz[rootX] += sz[rootY]; // Update the size of the merged set rooted at rootX
}
}
};
// Global Variables and Constants
const int MAXN = 200005; // Maximum number of vertices based on problem constraints
std::vector<std::vector<std::pair<int, int>>> adj; // Adjacency list representation of the graph: stores pairs {neighbor_vertex, edge_index}
std::vector<int> discovery_time; // Stores the discovery time of each vertex during DFS (for Tarjan's algorithm)
std::vector<int> low_link; // Stores the low-link value for each vertex during DFS (for Tarjan's algorithm)
std::vector<bool> visited; // Tracks visited vertices during the DFS traversal
int timer; // A global counter used to assign discovery times incrementally
std::vector<std::pair<int, int>> edge_list; // Stores pairs {u, v} corresponding to each edge index i (0 to M-1)
std::vector<bool> is_bridge_edge; // Boolean flag for each edge index, true if the edge is identified as a bridge
// Using std::function to define the type for the recursive bridge finding function.
// This allows defining the function implementation later or using lambdas.
std::function<void(int, int, int)> find_bridges_func;
// Implementation of Tarjan's bridge-finding algorithm using Depth First Search (DFS)
// u: current vertex, p: parent vertex in DFS tree, incoming_edge_idx: index of edge used to reach u from p
void find_bridges_impl(int u, int p, int incoming_edge_idx) {
visited[u] = true; // Mark the current vertex u as visited
discovery_time[u] = low_link[u] = timer++; // Initialize discovery time and low-link value for u
// Iterate through all edges connected to vertex u
for (auto& edge : adj[u]) {
int v = edge.first; // The neighbor vertex connected by this edge
int edge_idx = edge.second; // The unique index (0 to M-1) of this edge
// If the edge leads back to the parent 'p' through the same edge we arrived on, skip it.
// This prevents immediately traversing back along the edge used to enter 'u'.
if (edge_idx == incoming_edge_idx) continue;
if (visited[v]) {
// If neighbor 'v' is already visited:
// It means we found an edge to an already visited node. This could be a back edge to an ancestor
// or a cross edge to a node in another DFS subtree. In either case, update low_link[u].
// We can potentially reach an earlier discovered node (with smaller discovery time) via v.
low_link[u] = std::min(low_link[u], discovery_time[v]);
} else {
// If neighbor 'v' is not visited:
// It's a tree edge in the DFS tree. Recursively call DFS on 'v'.
// Pass 'u' as the parent and 'edge_idx' as the incoming edge index for the recursive call.
find_bridges_func(v, u, edge_idx);
// After the recursive call to v returns:
// Update low_link[u] based on the low_link value computed for v.
// If v or its descendants can reach an ancestor of u (indicated by low_link[v]),
// then u can also reach that ancestor via the path through v.
low_link[u] = std::min(low_link[u], low_link[v]);
// Check the bridge condition:
// An edge (u, v) is a bridge if and only if there is no back edge from v or its descendants
// to u or any ancestor of u. This condition is met if low_link[v] > discovery_time[u].
if (low_link[v] > discovery_time[u]) {
// If the condition holds, mark the edge identified by edge_idx as a bridge.
is_bridge_edge[edge_idx] = true;
}
}
}
}
// Main program execution starts here
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N, M, Q; // N: number of islands, M: number of connections, Q: number of queries
std::cin >> N >> M >> Q;
// Resize graph-related data structures based on N and M
adj.resize(N + 1); // Adjacency list for N+1 vertices (1-based indexing)
edge_list.resize(M); // List to store M edges
is_bridge_edge.assign(M, false); // Initialize all edges as non-bridges
discovery_time.resize(N + 1); // Resize DFS related vectors
low_link.resize(N + 1);
visited.resize(N + 1);
// Read M edge connections
for (int i = 0; i < M; ++i) {
int u, v;
std::cin >> u >> v;
// Add the edge to the adjacency list for both vertices u and v (undirected graph)
// Store the neighbor and the edge index 'i'
adj[u].push_back({v, i});
adj[v].push_back({u, i});
// Store the pair {u, v} associated with edge index 'i'
edge_list[i] = {u, v};
}
// Step 1: Find the connected components of the original graph G using DSU.
DSU dsu_G(N); // Initialize DSU for N vertices
for (int i = 0; i < M; ++i) {
// For each edge, unite the sets containing its endpoints
dsu_G.unite(edge_list[i].first, edge_list[i].second);
}
// Store the representative (component ID) for each vertex in G
std::vector<int> compG(N + 1);
for (int i = 1; i <= N; ++i) {
compG[i] = dsu_G.find(i);
}
// Step 2: Find all bridges in the graph G using Tarjan's algorithm.
// Assign the implementation function to the std::function variable
find_bridges_func = find_bridges_impl;
// Initialize DFS state variables before starting the traversal
std::fill(visited.begin() + 1, visited.end(), false); // Mark all vertices as unvisited
std::fill(discovery_time.begin() + 1, discovery_time.end(), -1); // Reset discovery times
std::fill(low_link.begin() + 1, low_link.end(), -1); // Reset low-link values
timer = 0; // Reset the global DFS timer
// Iterate through all vertices. If a vertex hasn't been visited, start a DFS from it.
// This ensures all connected components of the graph are processed.
for (int i = 1; i <= N; ++i) {
if (!visited[i]) {
// Start DFS from vertex i. Parent is -1 (none) and incoming edge index is -1 (none).
find_bridges_func(i, -1, -1);
}
}
// Step 3: Find the connected components of the graph G' which is G without its bridges.
DSU dsu_G_prime(N); // Initialize a new DSU structure for G'
// Iterate through all original edges
for (int i = 0; i < M; ++i) {
// If an edge is NOT a bridge (i.e., it's part of a cycle or biconnected component)
if (!is_bridge_edge[i]) {
// Unite its endpoints in the DSU structure for G'.
// This effectively builds components based on non-bridge edges.
dsu_G_prime.unite(edge_list[i].first, edge_list[i].second);
}
}
// Store the representative (component ID) for each vertex in G'
std::vector<int> compGprime(N + 1);
for (int i = 1; i <= N; ++i) {
compGprime[i] = dsu_G_prime.find(i);
}
// Step 4: Process the Q queries.
for (int q = 0; q < Q; ++q) {
int x, y;
std::cin >> x >> y; // Read the query pair (x, y)
// Check Condition 1: Are x and y in the same connected component in the original graph G?
bool connected_in_G = (compG[x] == compG[y]);
// Check Condition 2: Are x and y in different connected components in the graph G' (G without bridges)?
// Vertices in the same component in G' belong to the same non-trivial biconnected component in G.
bool different_components_in_Gprime = (compGprime[x] != compGprime[y]);
// A unique simple path exists between x and y if and only if both conditions are met:
// 1. They are connected in the original graph.
// 2. They do not belong to the same non-trivial biconnected component (which implies they are in different components in G').
if (connected_in_G && different_components_in_Gprime) {
std::cout << "Yes\n"; // If both conditions hold, output Yes
} else {
std::cout << "No\n"; // Otherwise, output No
}
}
return 0; // Indicate successful execution
}