結果

問題 No.922 東北きりきざむたん
ユーザー qwewe
提出日時 2025-05-14 13:20:29
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 112 ms / 2,000 ms
コード長 4,977 bytes
コンパイル時間 915 ms
コンパイル使用メモリ 81,540 KB
実行使用メモリ 21,540 KB
最終ジャッジ日時 2025-05-14 13:22:16
合計ジャッジ時間 4,587 ms
ジャッジサーバーID
（参考情報） 		judge5 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 26
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <vector>
#include <algorithm>

// Using 1-based indexing for cities
const int MAXN_NODES = 100005; 
const int LOGN_NODES = 18;    // ceil(log2(MAXN_NODES))

std::vector<int> adj[MAXN_NODES];
int comp_id[MAXN_NODES];           
bool visited_comp_dfs[MAXN_NODES]; 
int comp_reps[MAXN_NODES];         // Representative (root for LCA DFS) for each component ID
int current_comp_id_counter;

// For LCA
int depth[MAXN_NODES];
int parent_lca[MAXN_NODES][LOGN_NODES];

// For Median Sum
long long node_initial_weights[MAXN_NODES];      
long long subtree_total_node_weight[MAXN_NODES]; 
long long current_total_dist_sum[MAXN_NODES];    
long long min_dist_sum_for_this_comp;            

void find_components_dfs(int u, int c_id_val) {
    visited_comp_dfs[u] = true;
    comp_id[u] = c_id_val;
    for (int v : adj[u]) {
        if (!visited_comp_dfs[v]) {
            find_components_dfs(v, c_id_val);
        }
    }
}

void setup_lca_dfs(int u, int p, int d) {
    depth[u] = d;
    parent_lca[u][0] = p;
    for (int k = 1; k < LOGN_NODES; ++k) {
        if (parent_lca[u][k-1] == 0) parent_lca[u][k] = 0; // Optimization: if parent is 0, all higher parents are 0
        else parent_lca[u][k] = parent_lca[parent_lca[u][k - 1]][k - 1];
    }

    for (int v : adj[u]) {
        if (v == p) continue;
        setup_lca_dfs(v, u, d + 1);
    }
}

int get_lca(int u, int v) {
    if (depth[u] < depth[v]) std::swap(u, v);
    
    for (int k = LOGN_NODES - 1; k >= 0; --k) {
        if (parent_lca[u][k] != 0 && depth[u] - (1 << k) >= depth[v]) {
            u = parent_lca[u][k];
        }
    }

    if (u == v) return u;

    for (int k = LOGN_NODES - 1; k >= 0; --k) {
        if (parent_lca[u][k] != 0 && parent_lca[v][k] != 0 && parent_lca[u][k] != parent_lca[v][k]) {
            u = parent_lca[u][k];
            v = parent_lca[v][k];
        }
    }
    return parent_lca[u][0]; 
}

int query_dist_in_comp(int u, int v) {
    if (u == v) return 0;
    int lca_node = get_lca(u, v);
    return depth[u] + depth[v] - 2 * depth[lca_node];
}

void calculate_median_dfs1(int u, int p) {
    subtree_total_node_weight[u] = node_initial_weights[u];
    current_total_dist_sum[u] = 0;

    for (int v : adj[u]) {
        if (v == p) continue;
        calculate_median_dfs1(v, u);
        subtree_total_node_weight[u] += subtree_total_node_weight[v];
        current_total_dist_sum[u] += current_total_dist_sum[v] + subtree_total_node_weight[v];
    }
}

void calculate_median_dfs2(int u, int p, long long total_weight_for_comp) {
    min_dist_sum_for_this_comp = std::min(min_dist_sum_for_this_comp, current_total_dist_sum[u]);

    for (int v : adj[u]) {
        if (v == p) continue;
        current_total_dist_sum[v] = current_total_dist_sum[u] - subtree_total_node_weight[v] + (total_weight_for_comp - subtree_total_node_weight[v]);
        calculate_median_dfs2(v, u, total_weight_for_comp);
    }
}


int main() {
    std::ios_base::sync_with_stdio(false);
    std::cin.tie(NULL);

    int N_nodes, M_roads, Q_queries;
    std::cin >> N_nodes >> M_roads >> Q_queries;

    for (int i = 0; i < M_roads; ++i) {
        int u, v;
        std::cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    current_comp_id_counter = 0;
    for (int i = 1; i <= N_nodes; ++i) {
        if (!visited_comp_dfs[i]) {
            current_comp_id_counter++;
            comp_reps[current_comp_id_counter] = i; 
            find_components_dfs(i, current_comp_id_counter);
        }
    }
    
    for (int c = 1; c <= current_comp_id_counter; ++c) {
        setup_lca_dfs(comp_reps[c], 0, 0); 
    }
    
    std::vector<std::vector<int>> relevant_nodes_lists(current_comp_id_counter + 1);
    long long total_travel_distance = 0;

    for (int i = 0; i < Q_queries; ++i) {
        int u, v;
        std::cin >> u >> v;
        if (comp_id[u] == comp_id[v]) { 
            total_travel_distance += query_dist_in_comp(u, v);
        } else { 
            relevant_nodes_lists[comp_id[u]].push_back(u);
            relevant_nodes_lists[comp_id[v]].push_back(v);
        }
    }

    for (int c_id = 1; c_id <= current_comp_id_counter; ++c_id) {
        if (relevant_nodes_lists[c_id].empty()) {
            continue;
        }
        
        for (int node_val : relevant_nodes_lists[c_id]) {
            node_initial_weights[node_val]++;
        }
        
        long long current_total_node_weight = relevant_nodes_lists[c_id].size();

        int R_node = comp_reps[c_id]; 
        calculate_median_dfs1(R_node, 0); 
        
        min_dist_sum_for_this_comp = current_total_dist_sum[R_node]; 
        calculate_median_dfs2(R_node, 0, current_total_node_weight); 
        
        total_travel_distance += min_dist_sum_for_this_comp;

        for (int node_val : relevant_nodes_lists[c_id]) {
            node_initial_weights[node_val] = 0; 
        }
    }

    std::cout << total_travel_distance << std::endl;

    return 0;
}
0