結果

問題 No.772 Dynamic Distance Sum
ユーザー qwewe
提出日時 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
権限があれば一括ダウンロードができます

ソースコード

diff #

#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;
}
0