結果
問題 |
No.772 Dynamic Distance Sum
|
ユーザー |
![]() |
提出日時 | 2025-05-14 13:25:16 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
TLE
|
実行時間 | - |
コード長 | 6,016 bytes |
コンパイル時間 | 983 ms |
コンパイル使用メモリ | 95,100 KB |
実行使用メモリ | 11,172 KB |
最終ジャッジ日時 | 2025-05-14 13:26:13 |
合計ジャッジ時間 | 10,121 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 1 TLE * 1 -- * 25 |
ソースコード
#include <iostream> #include <vector> #include <map> #include <algorithm> #include <vector> // Adjacency list for naive (TLE) approach std::vector<std::map<int, int>> adj; // Stores {neighbor_node, edge_weight} std::vector<long long> X_values; // Stores X_v for each vertex v (0-indexed: X_values[v-1]) int N_nodes_global; // Number of nodes N long long total_sum_of_answers = 0; // Sum S for query decryption // DFS to find all nodes in the connected component of u void find_component_nodes(int u, std::vector<int>& component_nodes_list, std::vector<bool>& visited) { visited[u-1] = true; component_nodes_list.push_back(u); for (auto const& [neighbor, weight] : adj[u-1]) { if (!visited[neighbor-1]) { find_component_nodes(neighbor, component_nodes_list, visited); } } } // DFS to calculate sum of dist(root, v) * X_v for a specific root in its component void calculate_dist_sum_for_root(int u, int p, int root_node, long long current_distance, const std::vector<int>& component_ref, long long& current_sum_val) { // component_ref is not strictly needed here if adj only contains edges within component // but for safety, ensure we only sum for nodes in the component. // Since adj is global, we must ensure traversal stays within the component. // This check is implicitly handled by find_component_nodes + iterating through its output. if (X_values[u-1] == 1) { current_sum_val += current_distance; } for (auto const& [neighbor, weight] : adj[u-1]) { if (neighbor == p) continue; // Check if neighbor is in the same component. // This check is slow. A better way is to build a temporary adj list for the component. // Or pass visited array to ensure we only traverse component edges. bool in_component = false; for(int comp_node : component_ref) { if (neighbor == comp_node) { in_component = true; break; } } if (!in_component) continue; calculate_dist_sum_for_root(neighbor, u, root_node, current_distance + weight, component_ref, current_sum_val); } } int main() { std::ios_base::sync_with_stdio(false); std::cin.tie(NULL); int Q_queries; std::cin >> N_nodes_global >> Q_queries; adj.resize(N_nodes_global); X_values.assign(N_nodes_global, 1); // Initially all X_v = 1 for (int q_idx = 0; q_idx < Q_queries; ++q_idx) { int type; std::cin >> type; if (type == 1) { long long এ_enc, বি_enc; // Using non-ASCII to avoid variable name collision for a,b long long c_weight; std::cin >> এ_enc >> বি_enc >> c_weight; // Decrypt vertex numbers int u_node = (এ_enc - 1 + total_sum_of_answers) % N_nodes_global + 1; int v_node = (বি_enc - 1 + total_sum_of_answers) % N_nodes_global + 1; adj[u_node-1][v_node] = c_weight; adj[v_node-1][u_node] = c_weight; } else if (type == 2) { long long এ_enc, বি_enc; std::cin >> এ_enc >> বি_enc; // Decrypt vertex numbers int u_node = (এ_enc - 1 + total_sum_of_answers) % N_nodes_global + 1; int v_node = (বি_enc - 1 + total_sum_of_answers) % N_nodes_global + 1; adj[u_node-1].erase(v_node); adj[v_node-1].erase(u_node); } else { // type 3 long long এ_enc; std::cin >> এ_enc; // Decrypt vertex number int target_node_a = (এ_enc - 1 + total_sum_of_answers) % N_nodes_global + 1; // Flip X_value for target_node_a X_values[target_node_a-1] = 1 - X_values[target_node_a-1]; // Find connected component of target_node_a std::vector<int> component_nodes; std::vector<bool> visited_dfs(N_nodes_global, false); find_component_nodes(target_node_a, component_nodes, visited_dfs); if (component_nodes.empty()) { // Should not happen with valid inputs long long ans = 0; std::cout << ans << "\n"; total_sum_of_answers += ans; continue; } // Check if any X_v is 1 in the component bool active_node_exists = false; for(int node_in_comp : component_nodes) { if (X_values[node_in_comp-1] == 1) { active_node_exists = true; break; } } if (!active_node_exists) { // If all X_v are 0, sum is 0 for any root long long ans = 0; std::cout << ans << "\n"; total_sum_of_answers += ans; continue; } long long min_overall_dist_sum = -1; // Iterate over all nodes in the component, treat each as a potential root for (int root_candidate : component_nodes) { long long current_sum_for_this_root = 0; // DFS from root_candidate to calculate sum of dist * X_v // The component_nodes list is passed to ensure traversal stays within the component // for the calculate_dist_sum_for_root function. calculate_dist_sum_for_root(root_candidate, 0, root_candidate, 0, component_nodes, current_sum_for_this_root); if (min_overall_dist_sum == -1 || current_sum_for_this_root < min_overall_dist_sum) { min_overall_dist_sum = current_sum_for_this_root; } } std::cout << min_overall_dist_sum << "\n"; total_sum_of_answers += min_overall_dist_sum; } } return 0; }