結果
| 問題 |
No.1612 I hate Construct a Palindrome
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:18:20 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
WA
|
| 実行時間 | - |
| コード長 | 10,653 bytes |
| コンパイル時間 | 1,161 ms |
| コンパイル使用メモリ | 96,168 KB |
| 実行使用メモリ | 17,228 KB |
| 最終ジャッジ日時 | 2025-05-14 13:19:25 |
| 合計ジャッジ時間 | 10,909 ms |
|
ジャッジサーバーID （参考情報） |
judge1 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 28 WA * 6 TLE * 2 |
ソースコード
#include <iostream>
#include <vector>
#include <queue>
#include <string>
#include <vector>
#include <algorithm>
#include <tuple>
using namespace std;
// Using type aliases for clarity and brevity
using VI = vector<int>; // Vector of integers
using VC = vector<char>; // Vector of characters
using PII = pair<int, int>; // Pair of integers
// Tuple to represent an edge in the adjacency list: {neighbor_vertex, edge_label, edge_index}
template<typename T1, typename T2, typename T3>
using Tuple3 = tuple<T1, T2, T3>;
const int MAXN_glob = 100005; // Maximum number of vertices + 1
const int MAXM_glob = 200005; // Maximum number of edges + 1
// Adjacency list representation of the graph
// adj_glob[u] stores a list of tuples {v, label, edge_idx} for edges connected to vertex u
vector<Tuple3<int, char, int>> adj_glob[MAXN_glob];
// Array to store edge information (u, v, label) indexed by edge ID (1 to M)
// This allows quick lookup of edge label given its index
Tuple3<int, int, char> edge_info_glob[MAXM_glob + 1];
int N_glob, M_glob; // Global variables for number of vertices N and edges M
/**
* @brief Checks if a sequence of characters forms a palindrome.
*
* @param labels The vector of characters representing the sequence.
* @return true if the sequence is a palindrome, false otherwise.
*/
bool is_palindrome(const VC& labels) {
int k = labels.size();
// An empty string or a string with one character is considered a palindrome.
if (k <= 1) return true;
// Compare characters from the beginning and end moving inwards.
for (int i = 0; i < k / 2; ++i) {
if (labels[i] != labels[k - 1 - i]) {
return false; // If any pair doesn't match, it's not a palindrome.
}
}
return true; // All pairs matched, it's a palindrome.
}
int main() {
// Use fast I/O operations.
ios_base::sync_with_stdio(false);
cin.tie(NULL);
// Read the number of vertices N and edges M from input.
cin >> N_glob >> M_glob;
// Read M edges from input and populate the adjacency list and edge info array.
for (int i = 1; i <= M_glob; ++i) {
int u, v;
char c;
cin >> u >> v >> c; // Read vertices u, v and edge label c.
// Add edge to adjacency list for both u and v (since it's an undirected graph).
adj_glob[u].emplace_back(v, c, i);
adj_glob[v].emplace_back(u, c, i);
// Store edge info (u, v, label) associated with edge index i.
edge_info_glob[i] = make_tuple(u, v, c);
}
// Perform Breadth-First Search (BFS) starting from vertex 1 to find a shortest path to vertex N.
queue<int> q; // Queue for BFS
VI dist(N_glob + 1, -1); // distance[v] stores shortest distance from vertex 1 to v. Initialized to -1 (unvisited).
// parent[v] stores {previous_node, edge_index_used} to reach v in the shortest path from 1.
vector<PII> parent(N_glob + 1, {-1, -1});
q.push(1); // Start BFS from vertex 1.
dist[1] = 0; // Distance from source to itself is 0.
int final_node = -1; // Variable to confirm if vertex N was reached.
// BFS loop
while (!q.empty()) {
int u = q.front();
q.pop();
// If we reached the target vertex N, stop BFS.
if (u == N_glob) {
final_node = N_glob;
break;
}
// Explore neighbors of vertex u.
for (auto& edge : adj_glob[u]) {
int v = get<0>(edge); // Neighbor vertex
int edge_idx = get<2>(edge); // Index of the edge (u, v)
// If neighbor v has not been visited yet (distance is -1).
if (dist[v] == -1) {
dist[v] = dist[u] + 1; // Update distance to v.
parent[v] = {u, edge_idx}; // Set parent of v for path reconstruction.
q.push(v); // Add v to the queue to visit later.
}
}
}
// After BFS, check if vertex N was reachable from vertex 1.
if (final_node == -1) {
// The problem guarantees the graph is connected, so N should always be reachable if N >= 2.
// Output -1 if N is unreachable (this should theoretically not happen based on constraints).
cout << -1 << endl;
return 0;
}
// Reconstruct the shortest path from 1 to N using the parent pointers.
VI path_v; // Stores the sequence of vertices in the path.
VI path_e; // Stores the sequence of edge indices used in the path.
VC path_l; // Stores the sequence of edge labels along the path.
int curr = N_glob; // Start reconstruction from the target vertex N.
// Trace back parents until we reach the start vertex 1.
while (curr != 1) {
// Defensive check for errors during reconstruction.
if (parent[curr].first == -1 && curr != 1) {
cerr << "Error during path reconstruction: Parent indicates start node prematurely." << endl;
cout << -1 << endl; return 0;
}
int p_node = parent[curr].first; // Previous node in the path.
int edge_idx = parent[curr].second; // Index of the edge used to reach curr from p_node.
path_e.push_back(edge_idx); // Add edge index to path list.
// Retrieve the label of the edge using the stored edge info.
char label = get<2>(edge_info_glob[edge_idx]);
path_l.push_back(label); // Add label to path list.
path_v.push_back(curr); // Add current vertex to path list (will be reversed).
curr = p_node; // Move to the previous vertex.
}
path_v.push_back(1); // Add the starting vertex 1 to the path list.
// The path was reconstructed backwards (from N to 1), so reverse the sequences.
reverse(path_v.begin(), path_v.end()); // path_v now stores vertices 1...N
reverse(path_e.begin(), path_e.end()); // path_e now stores edge indices along 1...N
reverse(path_l.begin(), path_l.end()); // path_l now stores labels along 1...N
// Check if the label sequence of the found shortest path is a palindrome.
if (!is_palindrome(path_l)) {
// If it's not a palindrome, this path is a valid solution. Output it.
cout << path_e.size() << endl; // Output path length (number of edges).
for(int edge_idx : path_e) {
cout << edge_idx << endl; // Output each edge index on a new line.
}
return 0; // Solution found, terminate program.
}
// If the shortest path is a palindrome, we need to find a different path.
// Strategy: Try modifying the shortest path by inserting a small cycle (u -> w -> u).
int k = path_e.size(); // Length of the shortest path.
// Iterate through each vertex v_i on the shortest path (vertices are indexed 0 to k).
for (int i = 0; i < path_v.size(); ++i) {
int u = path_v[i]; // Current vertex v_i on the path.
// Iterate through all edges incident to vertex u.
for (auto& edge : adj_glob[u]) {
// int w = get<0>(edge); // Neighbor vertex w, not strictly needed here.
char c_prime = get<1>(edge); // Label of the edge (u, w).
int e_prime_idx = get<2>(edge); // Index of the edge (u, w).
// Construct the label sequence for the new path P' which includes the cycle u -> w -> u.
// The new path essentially goes 1... -> u -> w -> u -> ...N.
VC new_path_l; // Vector to store the labels of the modified path.
new_path_l.reserve(k + 2); // Reserve space for efficiency (length will be k+2).
// Part 1: Add labels from the original path before vertex v_i (edges e_1 to e_i).
// These correspond to labels path_l[0] through path_l[i-1].
for (int j = 0; j < i; ++j) {
new_path_l.push_back(path_l[j]);
}
// Part 2: Insert the labels corresponding to the cycle u -> w -> u.
// Both traversals use the same edge (u, w), so the label c_prime appears twice.
new_path_l.push_back(c_prime);
new_path_l.push_back(c_prime);
// Part 3: Add labels from the original path starting from vertex v_i (edges e_{i+1} to e_k).
// These correspond to labels path_l[i] through path_l[k-1].
for (int j = i; j < k; ++j) {
new_path_l.push_back(path_l[j]);
}
// Check if the modified path P' has a non-palindromic label sequence.
if (!is_palindrome(new_path_l)) {
// If non-palindromic, construct its edge index sequence.
VI new_path_e; // Vector to store edge indices of the modified path.
new_path_e.reserve(k + 2); // Reserve space for efficiency.
// Edges corresponding to Part 1 (before index i).
for(int j=0; j<i; ++j) {
new_path_e.push_back(path_e[j]);
}
// Edges corresponding to Part 2 (the cycle u -> w -> u).
// Edge index e_prime_idx is used twice.
new_path_e.push_back(e_prime_idx);
new_path_e.push_back(e_prime_idx);
// Edges corresponding to Part 3 (from index i onwards).
for(int j=i; j < k; ++j) {
new_path_e.push_back(path_e[j]);
}
// Check if the new path length exceeds the constraint 2*N.
// The length is k+2. Since k <= N-1 (shortest path), k+2 <= N+1.
// For N >= 1, N+1 <= 2N. Constraint is always satisfied if N>=1. Problem states N>=2.
if (new_path_e.size() > 2 * N_glob) {
// This condition should technically not be met given the logic above, but included as a safeguard.
continue; // Skip if path somehow exceeds length limit.
}
// Output the resulting path edge indices.
cout << new_path_e.size() << endl; // Output path length k+2.
for(int edge_idx : new_path_e) {
cout << edge_idx << endl; // Output each edge index.
}
return 0; // Solution found, terminate program.
}
}
}
// If the program reaches this point, it means the shortest path was a palindrome,
// and inserting any single cycle u -> w -> u at any vertex u on the path
// also resulted in a palindrome. In this case, we conclude no suitable path
// was found meeting the criteria (non-palindromic, length <= 2N).
cout << -1 << endl;
return 0;
}