結果
| 問題 |
No.2236 Lights Out On Simple Graph
|
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:07:21 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 200 ms / 4,000 ms |
| コード長 | 16,410 bytes |
| コンパイル時間 | 1,333 ms |
| コンパイル使用メモリ | 105,424 KB |
| 実行使用メモリ | 7,844 KB |
| 最終ジャッジ日時 | 2025-05-14 13:09:04 |
| 合計ジャッジ時間 | 3,520 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 57 |
コンパイルメッセージ
In file included from /usr/include/c++/13/string:51,
from /usr/include/c++/13/bits/locale_classes.h:40,
from /usr/include/c++/13/bits/ios_base.h:41,
from /usr/include/c++/13/ios:44,
from /usr/include/c++/13/ostream:40,
from /usr/include/c++/13/iostream:41,
from main.cpp:1:
In function ‘typename __gnu_cxx::__enable_if<std::__is_scalar<_Tp>::__value, void>::__type std::__fill_a1(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = bool*; _Tp = bool]’,
inlined from ‘void std::__fill_a(_FIte, _FIte, const _Tp&) [with _FIte = bool*; _Tp = bool]’ at /usr/include/c++/13/bits/stl_algobase.h:977:21,
inlined from ‘void std::fill(_ForwardIterator, _ForwardIterator, const _Tp&) [with _ForwardIterator = bool*; _Tp = bool]’ at /usr/include/c++/13/bits/stl_algobase.h:1007:20,
inlined from ‘int main()’ at main.cpp:224:9:
/usr/include/c++/13/bits/stl_algobase.h:931:18: warning: ‘void* __builtin_memset(void*, int, long unsigned int)’ specified bound between 18446744071562067968 and 18446744073709551615 exceeds maximum object size 9223372036854775807 [-Wstringop-overflow=]
931 | *__first = __tmp;
| ~~~~~~~~~^~~~~~~
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <map> // Use map for node mapping
#include <vector>
using namespace std;
// Define unsigned long long for bit manipulation, useful for M <= 64
typedef unsigned long long ull;
// Use built-in popcount if available (GCC/Clang), otherwise provide fallback
#ifdef __GNUC__
#define popcount(x) __builtin_popcountll(x)
#else
// Fallback popcount implementation counts set bits in ull
int popcount(ull n) {
int count = 0;
ull C = n; // Use a copy to avoid modifying input 'n'
while (C > 0) {
C &= (C - 1); // Clear the least significant bit set
count++;
}
return count;
}
#endif
// Constants for maximum N and M based on problem constraints
const int MAXN_const = 40;
const int MAXM_const = 40;
// Global storage for graph structure
vector<pair<int, int>> all_edges; // Stores all edges {u, v} as pairs of 0-indexed vertices
vector<vector<int>> node_to_edge_indices; // Map node index to list of edge indices incident to it
// DFS state variables
bool visited[MAXN_const]; // Track visited nodes during DFS
vector<int> component_nodes; // Store nodes (original 0-based indices) in the current component
vector<int> component_edge_indices; // Store edge indices (original 0-based indices) in the current component
// DFS function to find all nodes and edges belonging to a connected component starting from node u
void dfs_component(int u) {
visited[u] = true;
component_nodes.push_back(u);
// Iterate through edges incident to node u
for (int edge_idx : node_to_edge_indices[u]) {
// Find the other endpoint v of the edge
int v = all_edges[edge_idx].first == u ? all_edges[edge_idx].second : all_edges[edge_idx].first;
// Check if this edge has already been added to the component's edge list
bool edge_found = false;
for(int existing_edge_idx : component_edge_indices) {
if (edge_idx == existing_edge_idx) {
edge_found = true;
break;
}
}
// If not found, add it
if (!edge_found) {
component_edge_indices.push_back(edge_idx);
}
// If neighbor v hasn't been visited, recurse
if (!visited[v]) {
dfs_component(v);
}
}
}
/**
* Performs Gaussian elimination over F2 (modulo 2) on the system Ax = C.
* A is represented as a vector of ull, where each ull represents a row with bits corresponding to columns.
* C is the right-hand side vector.
* N is the number of rows (vertices in component), M is the number of columns (edges in component).
* Finds a basis for the null space (solutions to Ax = 0) and stores it in `basis`.
* Stores the original column index of the pivot variable for each row in `pivot_row_original_col`.
* Returns the rank of the matrix A. Returns -1 if the system is inconsistent (Ax=C has no solution).
*/
int gaussian_elimination(vector<ull>& A, vector<int>& C, int N, int M, vector<ull>& basis, vector<int>& pivot_row_original_col) {
basis.clear(); // Clear previous basis vectors
pivot_row_original_col.assign(N, -1); // Initialize pivot column info for each row
int rank = 0; // Current rank
vector<bool> is_pivot_col(M, false); // Track which columns contain a pivot
// Forward elimination phase
for (int current_col = 0; current_col < M && rank < N; ++current_col) {
// Find a row >= rank with a 1 in the current column
int pivot_row = rank;
while (pivot_row < N && !(A[pivot_row] & (1ULL << current_col))) {
pivot_row++;
}
// If no pivot found in this column, continue to the next column
if (pivot_row == N) continue;
// Swap the found pivot row with the current rank row
swap(A[rank], A[pivot_row]);
swap(C[rank], C[pivot_row]);
// Record the pivot information
pivot_row_original_col[rank] = current_col;
is_pivot_col[current_col] = true; // Mark this column as containing a pivot
// Eliminate 1s in the current column in all other rows
for (int i = 0; i < N; ++i) {
if (i != rank && (A[i] & (1ULL << current_col))) {
A[i] ^= A[rank]; // Row i = Row i + Row rank (mod 2)
C[i] ^= C[rank]; // C[i] = C[i] + C[rank] (mod 2)
}
}
rank++; // Increment rank
}
// Check for inconsistency: If any row after rank has C[i] = 1, system is inconsistent
for (int i = rank; i < N; ++i) {
if (C[i] == 1) {
return -1;
}
}
// Find basis for the null space Ax = 0
for (int j = 0; j < M; ++j) {
// If column j is not a pivot column, it corresponds to a free variable
if (!is_pivot_col[j]) {
ull b = (1ULL << j); // Create a basis vector starting with 1 at the free variable position j
// Determine the values of pivot variables for this basis vector
for (int r = 0; r < rank; ++r) {
int p_col = pivot_row_original_col[r]; // Pivot column for row r
// If the equation for row r (A[r]) involves the free variable x_j
if (A[r] & (1ULL << j)) {
// Set the corresponding pivot variable x_{p_col} to 1 to satisfy Ax = 0
b |= (1ULL << p_col);
}
}
basis.push_back(b); // Add the completed basis vector
}
}
return rank; // Return the rank of the matrix
}
/**
* Finds a particular solution xp to the system Ax = C (after Gaussian elimination).
* Uses back substitution, setting all free variables to 0.
* A and C are the matrix and vector after Gaussian elimination.
* N, M, rank are dimensions and rank.
* pivot_row_original_col maps row index to the column index of its pivot.
*/
ull find_particular_solution(const vector<ull>& A, const vector<int>& C, int N, int M, int rank, const vector<int>& pivot_row_original_col) {
ull xp = 0; // Initialize particular solution vector to all zeros
// Back substitution: iterate through rows from bottom (rank-1) up to 0
for (int r = rank - 1; r >= 0; --r) {
int p_col = pivot_row_original_col[r]; // The pivot variable column index for this row r
// If p_col is -1, it means row r is a zero row (should not happen for r < rank)
// Or there was an issue. For safety, skip if p_col invalid.
if (p_col == -1) {
continue;
}
int val = C[r]; // Target value for the equation represented by row r
// Calculate the contribution of already determined pivot variables (columns > p_col)
for (int c = p_col + 1; c < M; ++c) {
// Check if the equation for row r involves variable x_c
if (A[r] & (1ULL << c)) {
// Check if x_c is a pivot variable (not a free variable)
bool c_is_pivot = false;
for(int rr=0; rr < rank; ++rr){ // Check if column c is a pivot column for any row
if(pivot_row_original_col[rr] == c){
c_is_pivot = true;
break;
}
}
// If x_c is a pivot variable AND its value in xp (already determined) is 1
if(c_is_pivot && (xp & (1ULL << c))) {
val ^= 1; // Adjust the target value `val` based on x_c's contribution (mod 2)
}
// Note: Free variables are set to 0, so their contribution is always 0. No need to check them.
}
}
// After accounting for contributions from variables c > p_col, `val` is the required value for x_{p_col}.
if (val) { // If required value for the pivot variable x_{p_col} is 1
xp |= (1ULL << p_col); // Set the corresponding bit in xp
}
}
return xp; // Return the computed particular solution
}
int main() {
// Faster I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int N, M; // Number of vertices and edges
cin >> N >> M;
// Read edges and build adjacency list representation for edges incident to each node
all_edges.resize(M);
node_to_edge_indices.assign(N, vector<int>());
for (int i = 0; i < M; ++i) {
int u, v;
cin >> u >> v;
--u; --v; // Use 0-based indexing
all_edges[i] = {u, v};
node_to_edge_indices[u].push_back(i);
node_to_edge_indices[v].push_back(i);
}
// Read initial colors of vertices
vector<int> initial_colors(N);
for (int i = 0; i < N; ++i) {
cin >> initial_colors[i];
}
long long total_min_ops = 0; // Accumulator for the total minimum operations
fill(visited, visited + N, false); // Initialize visited array for DFS
// Iterate through all vertices to find connected components
for (int i = 0; i < N; ++i) {
if (!visited[i]) { // Found a start of a new component (or an isolated node)
component_nodes.clear(); // Reset component node list
component_edge_indices.clear(); // Reset component edge list
// Handle isolated nodes: if a node has no edges connected to it
if (node_to_edge_indices[i].empty()) {
visited[i] = true; // Mark as visited
// If an isolated node is black, it's impossible to make it white
if (initial_colors[i] == 1) {
cout << -1 << endl;
return 0;
}
// Isolated white node requires 0 operations, continue to next potential component
continue;
}
// Perform DFS to find all nodes and edges in the current connected component
dfs_component(i);
// Check the parity condition: number of black nodes in the component must be even
int current_comp_black_nodes = 0;
for (int node_idx : component_nodes) {
if (initial_colors[node_idx] == 1) {
current_comp_black_nodes++;
}
}
// If odd, impossible to solve
if (current_comp_black_nodes % 2 != 0) {
cout << -1 << endl;
return 0;
}
// If the component has nodes but no edges (should not happen if dfs starts from node with edges, but safety check)
if (component_edge_indices.empty()) {
// This implies all nodes in the component are isolated from each other within this component context.
// If any are black, impossible.
if (current_comp_black_nodes > 0) {
cout << -1 << endl; return 0;
}
// All nodes are white, requires 0 operations.
continue;
}
// Component size
int N_comp = component_nodes.size();
int M_comp = component_edge_indices.size();
// Create mappings from global node/edge indices to local 0..N_comp-1 / 0..M_comp-1 indices
map<int, int> node_map;
for(int j=0; j<N_comp; ++j) node_map[component_nodes[j]] = j;
map<int, int> edge_map;
for(int j=0; j<M_comp; ++j) edge_map[component_edge_indices[j]] = j;
// Build the incidence matrix A and target vector C for this component's linear system
vector<ull> A_comp(N_comp, 0ULL); // Matrix rows (one per node in component)
vector<int> C_comp(N_comp); // Target color vector (1 if black, 0 if white)
for(int j=0; j<N_comp; ++j) C_comp[j] = initial_colors[component_nodes[j]]; // Set target colors
// Populate the matrix A
for(int j=0; j<M_comp; ++j) {
int global_edge_idx = component_edge_indices[j]; // Original edge index
int u_global = all_edges[global_edge_idx].first; // Endpoint 1 (global index)
int v_global = all_edges[global_edge_idx].second; // Endpoint 2 (global index)
int edge_local_idx = j; // Local index for this edge (column index)
// Set bits in A matrix corresponding to the endpoints of the edge
if (node_map.count(u_global)) { // Check if u is in this component
int u_local = node_map[u_global]; // Get local index for u
A_comp[u_local] |= (1ULL << edge_local_idx); // Set bit for edge j in row u_local
}
if (node_map.count(v_global)) { // Check if v is in this component
int v_local = node_map[v_global]; // Get local index for v
A_comp[v_local] |= (1ULL << edge_local_idx); // Set bit for edge j in row v_local
}
}
// Solve the linear system Ax = C for this component
vector<ull> basis; // Basis vectors for the null space
vector<ull> A_copy = A_comp; // Copy A as GE modifies it
vector<int> C_copy = C_comp; // Copy C as GE modifies it
vector<int> pivot_row_original_col; // Stores pivot column indices found by GE
int rank = gaussian_elimination(A_copy, C_copy, N_comp, M_comp, basis, pivot_row_original_col);
// If system is inconsistent (should have been caught by parity check)
if (rank == -1) {
cout << -1 << endl;
return 0;
}
// Find one particular solution xp to Ax = C
ull xp = find_particular_solution(A_copy, C_copy, N_comp, M_comp, rank, pivot_row_original_col);
int k = basis.size(); // Number of free variables = dimension of null space
if (k == 0) { // If k=0, the solution xp is unique
total_min_ops += popcount(xp); // Add its weight (number of operations)
} else { // If k > 0, there are multiple solutions. Find the minimum weight one.
int min_comp_weight = MAXM_const + 1; // Initialize minimum weight to infinity
// Meet-in-the-middle approach: split basis into two halves
int k1 = k / 2;
int k2 = k - k1;
// Generate vectors y = xp + sum(alpha_i * b_i) for first half of basis vectors
vector<ull> listY; listY.reserve(1 << k1);
for(int mask = 0; mask < (1 << k1); ++mask) {
ull current_y = xp;
for(int bit = 0; bit < k1; ++bit) {
if((mask >> bit) & 1) { // If bit is set, XOR with corresponding basis vector
current_y ^= basis[bit];
}
}
listY.push_back(current_y);
}
// Generate vectors z = sum(alpha_j * b_j) for second half of basis vectors
vector<ull> listZ; listZ.reserve(1 << k2);
for(int mask = 0; mask < (1 << k2); ++mask) {
ull current_z = 0; // Start from zero vector
for(int bit = 0; bit < k2; ++bit) {
if((mask >> bit) & 1) { // If bit is set, XOR with corresponding basis vector (indices k1 to k-1)
current_z ^= basis[k1 + bit];
}
}
listZ.push_back(current_z);
}
// Find the minimum Hamming weight of y XOR z over all pairs (y from listY, z from listZ)
// This minimum weight corresponds to the minimum number of operations for this component.
min_comp_weight = MAXM_const + 1;
for (ull y : listY) {
for (ull z : listZ) {
min_comp_weight = min(min_comp_weight, popcount(y ^ z));
}
}
total_min_ops += min_comp_weight; // Add minimum weight for this component to total
}
}
}
// Output the total minimum number of operations
cout << total_min_ops << endl;
return 0;
}