G. Xor-MST

Codeforces

IDCF888G

Time2000ms

Memory256MB

Difficulty—

bitmasksconstructive algorithmsdata structures

English · Original

Chinese · Translation

Formal · Original

You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_. Calculate the weight of the minimum spanning tree in this graph. ## Input The first line contains _n_ (1 ≤ _n_ ≤ 200000) — the number of vertices in the graph. The second line contains _n_ integers _a_1, _a_2, ..., _a__n_ (0 ≤ _a__i_ < 230) — the numbers assigned to the vertices. ## Output Print one number — the weight of the minimum spanning tree in the graph. [samples]

给定一个具有 #cf_span[n] 个顶点的完全无向图。每个顶点被分配了一个数 #cf_span[ai]，且顶点 #cf_span[i] 与顶点 #cf_span[j] 之间的边的权重等于 #cf_span[ai xor aj]。计算该图的最小生成树的权重。第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。输出一个数——图中最小生成树的权重。 ## Input 第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。第二行包含 #cf_span[n] 个整数 #cf_span[a1], #cf_span[a2], ..., #cf_span[an] (#cf_span[0 ≤ ai < 230]) —— 分配给顶点的数。 ## Output 输出一个数——图中最小生成树的权重。 [samples]

Given a complete undirected graph with $ n $ vertices, where each vertex $ i $ is assigned a value $ a_i \in [0, 2^{30}) $, and the weight of edge $ (i, j) $ is $ a_i \oplus a_j $ (XOR), compute the weight of the minimum spanning tree (MST). **Formal Statement:** Let $ V = \{1, 2, \dots, n\} $, and let $ a : V \to \mathbb{Z} $ with $ 0 \leq a_i < 2^{30} $. Define the edge weight function $ w : V \times V \to \mathbb{Z}_{\geq 0} $ as: $$ w(i, j) = a_i \oplus a_j \quad \text{for all } i \ne j $$ Compute the total weight of the minimum spanning tree of the complete graph $ K_n $ with edge weights $ w(i, j) $. **Objective:** $$ \min_{T \in \mathcal{T}} \sum_{(i,j) \in E(T)} (a_i \oplus a_j) $$ where $ \mathcal{T} $ is the set of all spanning trees of $ K_n $.

Samples

Input #1

5
1 2 3 4 5

Output #1

Input #2

4
1 2 3 4

Output #2

API Response (JSON)

{
  "problem": {
    "name": "G. Xor-MST",
    "description": {
      "content": "You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_. Calcul",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 2000,
      "memory_limit": 262144
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF888G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given a complete undirected graph with _n_ vertices. A number _a__i_ is assigned to each vertex, and the weight of an edge between vertices _i_ and _j_ is equal to _a__i_ _xor_ _a__j_.\n\nCalcul...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个具有 #cf_span[n] 个顶点的完全无向图。每个顶点被分配了一个数 #cf_span[ai]，且顶点 #cf_span[i] 与顶点 #cf_span[j] 之间的边的权重等于 #cf_span[ai xor aj]。\n\n计算该图的最小生成树的权重。\n\n第一行包含 #cf_span[n] (#cf_span[1 ≤ n ≤ 200000]) —— 图中顶点的数量。\n\n第二行包含 #c...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "Given a complete undirected graph with $ n $ vertices, where each vertex $ i $ is assigned a value $ a_i \\in [0, 2^{30}) $, and the weight of edge $ (i, j) $ is $ a_i \\oplus a_j $ (XOR), compute the w...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments