結果
| 問題 |
No.2674 k-Walk on Bipartite
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:13:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 8,405 bytes |
| コンパイル時間 | 763 ms |
| コンパイル使用メモリ | 84,236 KB |
| 実行使用メモリ | 15,104 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:10 |
| 合計ジャッジ時間 | 3,675 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge1 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 32 WA * 4 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
using namespace std;
// Use a constant to represent infinity/unreachable distance.
// -1 is suitable as distances are non-negative.
const long long INF_DIST = -1;
int main() {
// Use faster I/O operations
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N; // Number of vertices
int M; // Number of edges in the given subset F
cin >> N >> M;
int s_node, t_node; // Source and target vertices (1-based indexing)
long long k; // Required walk length
cin >> s_node >> t_node >> k;
// Adjacency list to represent the graph (V, F)
vector<vector<int>> adj(N + 1);
// Read M edges and build the adjacency list
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
adj[u].push_back(v);
adj[v].push_back(u);
}
// --- Base case: k = 0 ---
// A walk of length 0 exists if and only if the start and end vertices are the same.
if (k == 0) {
if (s_node == t_node) {
cout << "Yes" << endl; // A walk of length 0 from s to s always exists.
} else {
cout << "No" << endl; // A walk of length 0 from s to t (s!=t) never exists.
}
return 0; // Exit after handling the base case.
}
// --- BFS from source s_node ---
// We perform BFS starting from s_node to:
// 1. Find the connected component containing s_node.
// 2. Compute the shortest path distances (d_min) from s_node to all reachable vertices.
// 3. Determine the bipartition (coloring vertices 0 or 1) for the component.
vector<long long> dist(N + 1, INF_DIST); // Stores shortest distance from s_node
vector<int> partition(N + 1, -1); // Stores partition info (0 or 1), -1 if unvisited
queue<int> q; // Queue for BFS
// Check if s_node has any neighbors in the given graph F.
// This is needed for the s=t, k>0 case.
bool s_has_neighbor = !adj[s_node].empty();
// Initialize BFS from s_node
dist[s_node] = 0;
partition[s_node] = 0; // Assign s_node to partition 0
q.push(s_node);
// Standard BFS loop
while (!q.empty()) {
int u = q.front();
q.pop();
for (int v : adj[u]) {
// If neighbor v hasn't been visited yet
if (dist[v] == INF_DIST) {
dist[v] = dist[u] + 1; // Update distance
partition[v] = 1 - partition[u]; // Assign to the opposite partition
q.push(v);
}
// The problem guarantees that the graph (V, F) is bipartite.
// So we don't need to check for consistency (e.g., edge between same partition vertices).
}
}
// --- Analyze reachability and parity ---
// Check if t_node is reachable from s_node in the graph (V, F)
if (dist[t_node] == INF_DIST) {
// If t_node is not reachable, s_node and t_node are in different connected components in (V, F).
// In this case, their relative partition assignment can potentially vary depending on how components
// are connected by additional edges in a potential supergraph H.
// This makes the existence of the walk dependent on H.
cout << "Unknown" << endl;
} else {
// If t_node is reachable, s_node and t_node are in the same connected component in (V, F).
// Their relative positions in any bipartition of any valid graph H are fixed.
long long d_min = dist[t_node]; // Shortest path distance in (V, F)
// Check the parity condition.
// A walk of length k between s_node and t_node can only exist if k has the same parity as d_min.
// This holds true for any bipartite graph containing (V, F).
if (k % 2 != d_min % 2) {
// If parity doesn't match, the walk is impossible in any bipartite graph H.
cout << "No" << endl;
} else {
// Parity matches. Now check if the walk MUST exist, MIGHT exist, or CANNOT exist.
// Check existence in the minimal graph H_min = (V, F)
bool walk_exists_in_min = false;
if (d_min <= k) { // A walk of length k is possible only if k is at least the shortest distance.
if (s_node == t_node) {
// If s_node == t_node and k > 0, a walk requires s_node to have at least one neighbor in F.
// This neighbor allows extending the path length by moving back and forth.
if (s_has_neighbor) {
walk_exists_in_min = true;
}
} else { // s_node != t_node
// If s_node != t_node, the shortest path has length d_min >= 1.
// The component must contain at least one edge.
// We can always extend the shortest path to length k by moving back and forth along an edge.
walk_exists_in_min = true;
}
}
if (walk_exists_in_min) {
// If a walk exists in H_min, it exists in all supergraphs H containing H_min.
cout << "Yes" << endl;
} else {
// Walk doesn't exist in H_min. This implies either:
// 1. k < d_min (desired length is shorter than shortest path)
// 2. s_node == t_node, k > 0, and s_node has no neighbors in F (isolated vertex case)
// Handle the special case: s_node == t_node and s_node is isolated in F.
if (s_node == t_node && !s_has_neighbor) {
// In this case, d_min = 0. Parity check (k % 2 == d_min % 2) implies k is even.
// Since we handled k=0 earlier, k must be a positive even integer.
// Walk doesn't exist in H_min because s_node is isolated.
// Could it exist in some H? Yes, if N >= 2, we could potentially add an edge (s_node, v)
// in a supergraph H, making the walk possible.
// Could it not exist? Yes, if H = H_min or no edges incident to s_node are added.
// Thus, the existence depends on H.
cout << "Unknown" << endl;
} else {
// The only remaining reason for walk not existing in H_min is k < d_min.
// Check walk existence in the conceptual maximal graph H_max.
// H_max is effectively a complete bipartite graph on the partitions L, R
// corresponding to the component containing s_node and t_node.
// The shortest path distance d_max in H_max depends on relative partitions.
long long d_max;
if (s_node == t_node) {
// If s_node == t_node, d_max is 0.
// We know s_node is not isolated (handled above), so the component has size > 1,
// meaning H_max has edges and walks are possible.
d_max = 0;
} else {
// partition[s_node] was initialized to 0. Check partition[t_node].
if (partition[t_node] == 1) { // s_node and t_node are in different partitions in H_max
d_max = 1; // Shortest path is direct edge s_node -> t_node
} else { // partition[t_node] == 0 => s_node and t_node are in the same partition
d_max = 2; // Shortest path is s_node -> v -> t_node via intermediate node v
}
}
// A walk of length k exists in H_max if and only if k >= d_max (since parity matches).
if (k >= d_max) {
// Walk exists in H_max but does not exist in H_min.
// This means the existence depends on the specific graph H.
cout << "Unknown" << endl;
} else {
// Walk doesn't exist even in H_max (because k < d_max).
// Since any H is a subgraph of H_max concept, walk cannot exist in any H.
cout << "No" << endl;
}
}
}
}
}
return 0;
}