結果
| 問題 |
No.1917 LCMST
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:12:46 |
| 言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
| 結果 |
AC
|
| 実行時間 | 379 ms / 4,000 ms |
| コード長 | 7,902 bytes |
| コンパイル時間 | 1,147 ms |
| コンパイル使用メモリ | 91,296 KB |
| 実行使用メモリ | 48,956 KB |
| 最終ジャッジ日時 | 2025-05-14 13:14:02 |
| 合計ジャッジ時間 | 15,901 ms |
|
ジャッジサーバーID （参考情報） |
judge3 / judge5 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 3 |
| other | AC * 42 |
ソースコード
#include <iostream>
#include <vector>
#include <numeric>
#include <algorithm>
#include <tuple>
#include <limits> // Needed for numeric_limits
// Define long long type for potentially large costs
typedef long long ll;
// Define the maximum possible value for A_i based on problem constraints
const int MAX_VAL = 100005;
// Global arrays to store counts and presence of A_i values
int count[MAX_VAL]; // Stores count of each A_i value
bool present[MAX_VAL]; // Tracks which A_i values are present in the input
std::vector<int> distinct_values; // Stores the distinct A_i values present in the input
// Disjoint Set Union (DSU) structure
struct DSU {
std::vector<int> parent;
// Constructor initializes DSU for elements indexed 1 to n. Array size n+1.
DSU(int n) {
parent.resize(n + 1);
// Initialize each element as its own parent
std::iota(parent.begin(), parent.end(), 0);
}
// Find the representative (root) of the set containing x, with path compression optimization
int find(int x) {
if (parent[x] == x) {
return x;
}
// Path compression: set parent directly to the root
return parent[x] = find(parent[x]);
}
// Unite the sets containing x and y
void unite(int x, int y) {
int rootX = find(x);
int rootY = find(y);
// If they are not already in the same set, merge them
if (rootX != rootY) {
// Simple merge: make rootX child of rootY. Could use union by rank/size for further optimization.
parent[rootX] = rootY;
}
}
};
// Computes greatest common divisor (GCD) using Euclidean algorithm
ll gcd(ll a, ll b) {
while (b) {
a %= b;
std::swap(a, b);
}
return a;
}
// Computes least common multiple (LCM) using the formula lcm(a, b) = (a / gcd(a, b)) * b
// This implementation assumes the final LCM result fits within a 64-bit long long,
// based on problem constraints (max A_i = 10^5, max LCM approx 10^10).
ll lcm(ll a, ll b) {
// Handle edge case where a or b is 0
if (a == 0 || b == 0) return 0;
// Compute GCD first
ll common_divisor = gcd(a, b);
// If GCD is 0, should not happen for positive a, b
if (common_divisor == 0) return 0;
// Calculate (a / gcd(a, b)) first. This reduces the magnitude before multiplication,
// helping to prevent intermediate overflow.
ll term1 = a / common_divisor;
// Perform the final multiplication. Potential overflow check using 128-bit integers
// is possible with GCC/Clang (#ifdef __GNUC__ ... unsigned __int128 ...) but omitted
// here for simplicity and assuming constraints guarantee result fits in long long.
return term1 * b;
}
// multiples[g] will store a list of distinct values k present in the input A array such that g divides k
std::vector<int> multiples[MAX_VAL];
int main() {
// Use fast I/O operations
std::ios_base::sync_with_stdio(false);
std::cin.tie(NULL);
int N; // Number of vertices
std::cin >> N;
int max_A = 0; // Track the maximum A_i value encountered
// Read input values A_i
for (int i = 0; i < N; ++i) {
int A_i;
std::cin >> A_i;
// Record presence and count of A_i
if (!present[A_i]) { // If seeing this value for the first time
present[A_i] = true;
distinct_values.push_back(A_i); // Add to list of distinct values
}
count[A_i]++; // Increment count for this value
// Update maximum A_i value seen so far
if (A_i > max_A) {
max_A = A_i;
}
}
ll total_cost = 0; // Initialize total MST cost
// Step 1: Calculate initial MST cost within groups of vertices having the same A_i value.
// For each distinct value k present in the input:
// All count[k] vertices with value k form a clique where edges have weight lcm(k, k) = k.
// To connect these count[k] vertices into one component, we need count[k]-1 edges of weight k.
for (int k : distinct_values) {
total_cost += (ll)(count[k] - 1) * k;
}
// Precompute the list of multiples for each potential GCD value g up to max_A.
// This helps efficiently find pairs (k, l) related by a common divisor g later.
for (int g = 1; g <= max_A; ++g) {
// Iterate through all multiples k of g up to max_A
for (int k = g; k <= max_A; k += g) {
// If k is one of the values present in the input A array
if (present[k]) {
// Add k to the list of multiples for g
multiples[g].push_back(k);
}
}
}
// Stores potential edges for the MST calculation between components of distinct values.
// Each tuple is (weight, u, v) where weight = lcm(u, v).
std::vector<std::tuple<ll, int, int>> potential_edges;
// Step 2: Generate candidate edges connecting components based on GCD property.
// This approach is derived from a technique used in similar competitive programming problems.
// It generates a set of edges guaranteed to contain the MST edges connecting the components.
// Iterate through all possible GCD values g from 1 up to max_A
for (int g = 1; g <= max_A; ++g) {
// If there are fewer than 2 multiples of g present among the distinct A_i values,
// we cannot form an edge based on this GCD g.
if (multiples[g].size() < 2) continue;
// Find the minimum value k_min among the multiples of g present in the input.
// This node k_min acts as a hub for connecting other multiples of g.
int min_k = multiples[g][0];
for(size_t i = 1; i < multiples[g].size(); ++i){
if(multiples[g][i] < min_k) min_k = multiples[g][i];
}
// Add potential edges connecting k_min to all other multiples k of g.
// The edge weight is lcm(k, k_min).
for (int k : multiples[g]) {
if (k != min_k) { // Don't add edge from min_k to itself
potential_edges.emplace_back(lcm((ll)k, (ll)min_k), k, min_k);
}
}
}
// Sort the generated potential edges by their weight (LCM value) in non-decreasing order.
std::sort(potential_edges.begin(), potential_edges.end());
// Step 3: Run Kruskal's algorithm on the components representing distinct values.
// Use DSU structure initialized for values up to max_A.
DSU dsu(max_A);
int num_distinct_values = distinct_values.size();
int edges_count = 0; // Count number of edges added to connect the components
// If there's only 0 or 1 distinct value type, the graph is already connected (or empty).
// The initial cost calculated in Step 1 is the final answer.
if (num_distinct_values > 1) {
// Iterate through sorted potential edges
for (const auto& edge : potential_edges) {
ll weight;
int u, v;
std::tie(weight, u, v) = edge; // Unpack edge tuple
// Check if the components containing u and v are already connected
if (dsu.find(u) != dsu.find(v)) {
// If not connected, add this edge to the MST
dsu.unite(u, v); // Merge the components
total_cost += weight; // Add the edge weight to the total MST cost
edges_count++; // Increment the count of edges added
// We need exactly num_distinct_values - 1 edges to connect all components.
// If we have added enough edges, stop Kruskal's algorithm.
if (edges_count == num_distinct_values - 1) {
break;
}
}
}
}
// Output the final total MST cost
std::cout << total_cost << std::endl;
return 0;
}