G. Shortest Path Queries

Codeforces

IDCF938G

Time3000ms

Memory512MB

Difficulty—

bitmasksdata structuresdsugraphs

English · Original

Chinese · Translation

Formal · Original

You are given an undirected connected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is traversed more than once, then it is included in bitwise xor the same number of times). There are three types of queries you have to process: * 1 _x_ _y_ _d_ — add an edge connecting vertex _x_ to vertex _y_ with weight _d_. It is guaranteed that there is no edge connecting _x_ to _y_ before this query; * 2 _x_ _y_ — remove an edge connecting vertex _x_ to vertex _y_. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query; * 3 _x_ _y_ — calculate the length of the shortest path (possibly non-simple) from vertex _x_ to vertex _y_. Print the answers for all queries of type 3. ## Input The first line contains two numbers _n_ and _m_ (1 ≤ _n_, _m_ ≤ 200000) — the number of vertices and the number of edges in the graph, respectively. Then _m_ lines follow denoting the edges of the graph. Each line contains three integers _x_, _y_ and _d_ (1 ≤ _x_ < _y_ ≤ _n_, 0 ≤ _d_ ≤ 230 - 1). Each pair (_x_, _y_) is listed at most once. The initial graph is connected. Then one line follows, containing an integer _q_ (1 ≤ _q_ ≤ 200000) — the number of queries you have to process. Then _q_ lines follow, denoting queries in the following form: * 1 _x_ _y_ _d_ (1 ≤ _x_ < _y_ ≤ _n_, 0 ≤ _d_ ≤ 230 - 1) — add an edge connecting vertex _x_ to vertex _y_ with weight _d_. It is guaranteed that there is no edge connecting _x_ to _y_ before this query; * 2 _x_ _y_ (1 ≤ _x_ < _y_ ≤ _n_) — remove an edge connecting vertex _x_ to vertex _y_. It is guaranteed that there was such edge in the graph, and the graph stays connected after this query; * 3 _x_ _y_ (1 ≤ _x_ < _y_ ≤ _n_) — calculate the length of the shortest path (possibly non-simple) from vertex _x_ to vertex _y_. It is guaranteed that at least one query has type 3. ## Output Print the answers for all queries of type 3 in the order they appear in input. [samples]

给定一个带权无向连通图。两点间某条路径的长度定义为该路径上所有边权的异或和（若某条边被经过多次，则在异或和中被包含相同次数）。你需要处理三种类型的查询：请输出所有类型为 #cf_span[3] 的查询的答案。第一行包含两个数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 200000]），分别表示图的顶点数和边数。接下来 #cf_span[m] 行，每行描述一条边，包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[d]（#cf_span[1 ≤ x < y ≤ n]，#cf_span[0 ≤ d ≤ 230 - 1]）。每对 #cf_span[(x, y)] 最多出现一次。初始图是连通的。接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 200000]），表示需要处理的查询数量。接下来 #cf_span[q] 行，每行描述一个查询，格式如下：保证至少有一个查询类型为 #cf_span[3]。请按输入顺序输出所有类型为 #cf_span[3] 的查询的答案。 ## Input 第一行包含两个数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 200000]），分别表示图的顶点数和边数。接下来 #cf_span[m] 行，每行描述一条边，包含三个整数 #cf_span[x]、#cf_span[y] 和 #cf_span[d]（#cf_span[1 ≤ x < y ≤ n]，#cf_span[0 ≤ d ≤ 230 - 1]）。每对 #cf_span[(x, y)] 最多出现一次。初始图是连通的。接下来一行包含一个整数 #cf_span[q]（#cf_span[1 ≤ q ≤ 200000]），表示需要处理的查询数量。接下来 #cf_span[q] 行，每行描述一个查询，格式如下： #cf_span[1] #cf_span[x] #cf_span[y] #cf_span[d]（#cf_span[1 ≤ x < y ≤ n]，#cf_span[0 ≤ d ≤ 230 - 1]）——添加一条连接顶点 #cf_span[x] 和 #cf_span[y]、权重为 #cf_span[d] 的边。保证在此查询前不存在连接 #cf_span[x] 和 #cf_span[y] 的边； #cf_span[2] #cf_span[x] #cf_span[y]（#cf_span[1 ≤ x < y ≤ n]）——移除一条连接顶点 #cf_span[x] 和 #cf_span[y] 的边。保证图中存在该边，且移除后图仍保持连通； #cf_span[3] #cf_span[x] #cf_span[y]（#cf_span[1 ≤ x < y ≤ n]）——计算从顶点 #cf_span[x] 到顶点 #cf_span[y] 的最短路径（可能非简单路径）的长度。保证至少有一个查询类型为 #cf_span[3]。 ## Output 请按输入顺序输出所有类型为 #cf_span[3] 的查询的答案。 [samples]

**Definitions** Let $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $. Each edge $ e = (x, y) \in E $ has a weight $ w(e) \in \mathbb{Z} $, $ 0 \le w(e) \le 2^{30} - 1 $. For any path $ P $ between two vertices, define its **length** as the bitwise XOR of weights of all edges in $ P $, counting multiplicity (i.e., if an edge is traversed $ k $ times, it is XORed $ k $ times). Let $ \mathcal{Q} $ be a sequence of $ q $ queries of three types: - **Type 1**: Add a new edge $ (x, y, d) $ to $ G $. - **Type 2**: Remove an existing edge $ (x, y) $ from $ G $. - **Type 3**: Query the XOR distance between vertices $ x $ and $ y $, i.e., the XOR length of any path between them. **Constraints** 1. $ 1 \le n, m \le 200000 $ 2. $ 1 \le q \le 200000 $ 3. For each edge $ (x, y, d) $: $ 1 \le x < y \le n $, $ 0 \le d \le 2^{30} - 1 $ 4. Initial graph is connected. 5. Each edge $ (x, y) $ appears at most once in input. 6. Type 2 queries only remove edges that currently exist. 7. Type 3 queries are guaranteed to appear at least once. **Objective** For each query of type 3 with parameters $ (x, y) $, output the XOR distance between $ x $ and $ y $ in the current graph.

Samples

Input #1

Output #1

1
1
2

API Response (JSON)

{
  "problem": {
    "name": "G. Shortest Path Queries",
    "description": {
      "content": "You are given an undirected connected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is travers",
      "description_type": "Markdown"
    },
    "platform": "Codeforces",
    "limit": {
      "time_limit": 3000,
      "memory_limit": 524288
    },
    "difficulty": "None",
    "is_remote": true,
    "is_sync": true,
    "sync_url": null,
    "sign": "CF938G"
  },
  "statements": [
    {
      "statement_type": "Markdown",
      "content": "You are given an undirected connected graph with weighted edges. The length of some path between two vertices is the bitwise xor of weights of all edges belonging to this path (if some edge is travers...",
      "is_translate": false,
      "language": "English"
    },
    {
      "statement_type": "Markdown",
      "content": "给定一个带权无向连通图。两点间某条路径的长度定义为该路径上所有边权的异或和（若某条边被经过多次，则在异或和中被包含相同次数）。\n\n你需要处理三种类型的查询：\n\n请输出所有类型为 #cf_span[3] 的查询的答案。\n\n第一行包含两个数 #cf_span[n] 和 #cf_span[m]（#cf_span[1 ≤ n, m ≤ 200000]），分别表示图的顶点数和边数。\n\n接下来 #cf_spa...",
      "is_translate": true,
      "language": "Chinese"
    },
    {
      "statement_type": "Markdown",
      "content": "**Definitions**  \nLet $ G = (V, E) $ be an undirected connected graph with $ |V| = n $, $ |E| = m $.  \nEach edge $ e = (x, y) \\in E $ has a weight $ w(e) \\in \\mathbb{Z} $, $ 0 \\le w(e) \\le 2^{30} - 1 ...",
      "is_translate": false,
      "language": "Formal"
    }
  ]
}

Full JSON Raw Segments