結果
| 問題 |
No.1400 すごろくで世界旅行
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:06:09 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 70 ms / 3,153 ms |
| コード長 | 10,147 bytes |
| コンパイル時間 | 886 ms |
| コンパイル使用メモリ | 88,740 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:07:10 |
| 合計ジャッジ時間 | 2,606 ms |
|
ジャッジサーバーID （参考情報） |
judge5 / judge2 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 18 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <queue>
#include <bitset>
#include <string>
// Define the maximum number of vertices based on problem constraints.
// Using a constant ensures bitset size is known at compile time.
const int MAXV = 2000;
// Global storage for the adjacency information using std::vector of std::bitset.
// This allows dynamic resizing based on input V, while bitsets provide efficient row operations.
std::vector<std::bitset<MAXV>> adj;
int V; // Number of vertices
long long D; // Number of turns
// Matrix struct definition for boolean matrix operations.
// It holds the matrix data as a vector of bitsets.
struct Matrix {
std::vector<std::bitset<MAXV>> mat;
// Default constructor.
Matrix() {}
// Resizes the matrix to `size` x `size`. Bitsets are default-initialized to all zeros.
void resize(int size) {
mat.resize(size);
}
// Creates an identity matrix of a given size.
// Diagonal elements are set to 1, others remain 0.
static Matrix identity(int size) {
Matrix I;
I.resize(size);
for (int i = 0; i < size; ++i) {
// Check index boundary for safety, although V <= MAXV is expected.
if (i < MAXV) {
I.mat[i][i] = 1;
}
}
return I;
}
// Performs boolean matrix multiplication: C = this * other.
// Uses bitset operations for optimization. The complexity is O(V^3 / w) where w is word size.
Matrix multiply(const Matrix& other) const {
Matrix result;
result.resize(V); // Result matrix also has size V x V.
// The core logic for boolean matrix multiplication with bitsets:
// For each element A[i][k] that is 1, OR the k-th row of B into the i-th row of C.
// A is `this->mat`, B is `other.mat`, C is `result.mat`.
for (int i = 0; i < V; ++i) {
for (int k = 0; k < V; ++k) {
if (this->mat[i][k]) { // If the bit A[i][k] is set
// Perform bitwise OR operation. Efficient for std::bitset.
result.mat[i] |= other.mat[k];
}
}
}
return result;
}
};
// Computes matrix power base^exp using binary exponentiation (also known as exponentiation by squaring).
// This significantly reduces the number of matrix multiplications required, to O(log exp).
Matrix matrix_pow(Matrix base, long long exp) {
Matrix res = Matrix::identity(V); // Initialize result to identity matrix.
// Base matrix `base` is assumed to be V x V.
while (exp > 0) {
if (exp % 2 == 1) { // If the current least significant bit of exponent is 1
res = res.multiply(base); // Multiply result by the current power of base.
}
base = base.multiply(base); // Square the base for the next iteration.
exp /= 2; // Right shift exponent to process the next bit.
}
return res; // Return the final computed matrix power.
}
// Checks if the graph is connected using Breadth-First Search (BFS).
// Assumes V >= 1. It should be called after checking that all vertices have degree >= 1.
bool is_connected() {
// Base cases: A graph with 0 or 1 vertex is considered connected.
if (V <= 1) return true;
std::vector<bool> visited(V, false); // Track visited vertices during BFS.
std::queue<int> q; // Queue for BFS traversal.
// Start BFS from vertex 0. Since graph has edges (degrees >= 1), any vertex works as starting point if connected.
q.push(0);
visited[0] = true;
int count = 0; // Count the number of vertices reached.
while (!q.empty()) {
int u = q.front();
q.pop();
count++;
// Explore neighbors of vertex u.
for (int v = 0; v < V; ++v) {
// Check edge existence using the global adjacency list `adj`.
if (adj[u][v] && !visited[v]) { // If v is a neighbor and hasn't been visited yet.
visited[v] = true; // Mark v as visited.
q.push(v); // Add v to the queue for exploration.
}
}
}
// If the number of visited vertices equals V, the entire graph is reachable from vertex 0, hence connected.
return count == V;
}
// Checks if the graph is bipartite using BFS and 2-coloring.
// Returns true if the graph is bipartite, false otherwise. Non-bipartite graphs contain odd cycles or self-loops (for V>1).
bool is_bipartite() {
// Base case: An empty graph (V=0) is bipartite. A graph with 1 vertex is also bipartite.
if (V == 0) return true;
std::vector<int> color(V, -1); // Store color (-1: uncolored, 0: color 0, 1: color 1).
// Iterate through all vertices to handle potentially disconnected components.
// Although called after connectivity check, this ensures correctness even if used independently.
for (int start_node = 0; start_node < V; ++start_node) {
if (color[start_node] == -1) { // If vertex hasn't been colored yet, start BFS from it.
std::queue<int> q;
q.push(start_node);
color[start_node] = 0; // Assign the first color (0).
while (!q.empty()) {
int u = q.front();
q.pop();
// Check all potential neighbors v of u.
for (int v = 0; v < V; ++v) {
if (adj[u][v]) { // If there is an edge between u and v.
if (color[v] == -1) { // If neighbor v is uncolored.
color[v] = 1 - color[u]; // Assign the opposite color to v.
q.push(v); // Add v to queue for further exploration.
} else if (color[v] == color[u]) { // If neighbor v has the same color as u.
// Conflict detected! An edge connects two nodes of the same color.
// This means the graph has an odd cycle or a self-loop (if u == v). It's not bipartite.
return false;
}
// If neighbor v has the opposite color, it's consistent with bipartiteness. Continue.
}
}
}
}
}
// If the BFS completes for all components without finding any color conflicts, the graph is bipartite.
return true;
}
int main() {
// Optimize standard I/O operations for faster execution.
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
// Read number of vertices V and number of turns D from input.
std::cin >> V >> D;
// Initialize adjacency structures.
adj.resize(V); // Resize global adjacency list vector.
Matrix A; // Matrix A represents the adjacency matrix for exponentiation.
A.resize(V); // Resize matrix A to V x V.
std::vector<int> degrees(V, 0); // Vector to store vertex degrees.
// Read the adjacency matrix representation from input.
for (int i = 0; i < V; ++i) {
std::string row_str; // Read the i-th row as a string.
std::cin >> row_str;
for (int j = 0; j < V; ++j) {
if (row_str[j] == '1') { // If E_ij = 1, indicating an edge.
A.mat[i][j] = 1; // Set the corresponding bit in matrix A.
adj[i][j] = 1; // Set the bit in the global adjacency list `adj`.
degrees[i]++; // Increment the degree count for vertex i.
}
}
}
// === Initial Necessary Condition Checks ===
// Check 1: Every vertex must have at least one outgoing edge (degree >= 1).
// This is required because the piece must be moved every turn.
for (int i = 0; i < V; ++i) {
if (degrees[i] == 0) {
std::cout << "No" << std::endl; // If any vertex has degree 0, it's impossible.
return 0;
}
}
// Check 2: The graph must be connected.
// If not, some pairs (i, j) are unreachable regardless of path length.
if (!is_connected()) {
std::cout << "No" << std::endl;
return 0;
}
// Check 3: If V > 1, the graph must not be bipartite.
// In a bipartite graph, reachability depends on path length parity, so not all vertices are reachable from all others in *exactly* D steps.
if (V > 1 && is_bipartite()) {
std::cout << "No" << std::endl;
return 0;
}
// === Main Logic based on checks ===
// If the graph passed all preliminary checks, proceed.
// Base case: If V=1, the degree check implies E_11=1. It's always possible to stay at vertex 1 for D turns.
if (V == 1) {
std::cout << "Yes" << std::endl;
return 0;
}
// Check 4: Check if D is sufficiently large using the primitivity theorem bound.
// For connected, non-bipartite graphs, A^k has all positive entries for k >= N.
// The bound N = V^2 - 2V + 2 is known for primitive matrices. Use long long for calculation.
long long N_threshold = (long long)V * V - 2LL * V + 2;
// If D is greater than or equal to this threshold, reachability is guaranteed.
if (D >= N_threshold) {
std::cout << "Yes" << std::endl;
return 0;
}
// Check 5: If D is smaller than the threshold, compute A^D explicitly.
// Use the matrix exponentiation function defined earlier.
Matrix AD = matrix_pow(A, D);
// Check if all entries in the resulting matrix AD are 1.
bool ok = true; // Assume initially that all entries are 1.
for (int i = 0; i < V; ++i) {
// Use bitset::count() method which returns the number of set bits. Check if it equals V.
if (AD.mat[i].count() != V) {
ok = false; // Found a row that doesn't have all bits set, meaning some entry is 0.
break; // No need to check further rows.
}
}
// Output the final result based on whether AD has all entries 1.
if (ok) {
std::cout << "Yes" << std::endl;
} else {
std::cout << "No" << std::endl;
}
return 0; // End of program.
}