問題一覧 > 通常問題

No.2294 Union Path Query (Easy)

レベル : / AI推定難易度 : 1700 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 27
作問者 : t98slider / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 9155 / 自分の提出
問題文最終更新日: 2023-05-11 02:56:26
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder contest 387 (Union Find Contest) (順位表) の他の問題:

Problem Statement

There are a weighted undirected graph $G$ with $N$ vertices and $0$ edges, and a variable $X$. The vertices of the graph are numbered from $0$ to $N-1$ .
The variable $X$ is initially set to $ X_{0} $.
The distance ${\rm dist} (u, v) $ between 2 vertices $u$, $v$ in the graph $G$ is defined as follows.
$$ {\rm dist} (u, v) = 頂点\ u\ から頂点\ v\ への単純パスに含まれる辺すべての重みの{\rm XOR} $$ The distance from a vertex to itself is ${\rm dist}(v, v) = 0$.
You are given $Q$ queries of the following forms. Process them in order on the graph $G$ and the variable $X$.

  • 1 v w: Connect vertex $v$ and vertex $X$ with an edge of weight $w$. It is guaranteed that in the given input this operation does not create a cycle in the graph $G$.
  • 2 u v: If vertex $u$ and vertex $v$ are not connected, output -1. If they are connected, output ${\rm dist} (u, v) $ and add ${\rm dist} (u, v) $ to $X$.
    Then, replace $X$ with its remainder modulo $N$.
  • 3 v: Output the sum of the distances over all pairs of vertices in the same connected component as vertex $v$, modulo $998244353$.
    That is, letting $K$ be the number of vertices connected to vertex $v$ (including vertex $v$ itself), and denoting them by $ u = (u_{1}, u_{2}, u_{3}, \cdots, u_{K})$, output $$ \left( \sum_{i=2}^{K}\sum_{j=1}^{i-1} {\rm dist}(u_{i}, u_{j}) \right) \bmod\ 998244353 $$ . If there is only $1$ vertex connected to vertex $v$ (only vertex $v$ itself), output 0.
  • 4 value: Add the value ${\rm value}$ to $X$. Then, replace $X$ with its remainder modulo $N$.

Input

$N\ X_{0}\ Q$
${\rm Query}_{1}$
${\rm Query}_{2}$
${\rm Query}_{3}$
$\ \ \ \ \vdots$
${\rm Query}_{i}$
$\ \ \ \ \vdots$
${\rm Query}_{Q}$

  • $1 \leq N \leq 2 \times 10^{5}$
  • $1 \leq Q \leq 3 \times 10^{5}$
  • $0 \leq X_{0} < N$
  • For ${\rm Query}_{i}$:

    For a type 1 query
    $1\ v_{i}\ w_{i}$
    For a type 2 query
    $2\ u_{i}\ v_{i}$
    For a type 3 query
    $3\ v_{i}$
    For a type 4 query
    $4\ {\rm value}_{i}$
    ・$0 \leq u_{i}, v_{i}, {\rm value}_{i} < N$
    ・$0 \leq w_{i} < 2^{30}$
    ・It is guaranteed that type 1 queries do not create a cycle in the graph $G$.

  • All input values are integers.

Output

Let $K$ be the total number of type 2 and type 3 queries given. On line $i\ (1 \leq i \leq K)$, output the answer to the corresponding query in 1 line. Print a newline at the end.

Sample

Sample 1
Input
5 1 11
1 0 1
2 0 1
2 0 2
1 0 2
3 1
4 4
1 3 5
3 3
2 3 2
1 4 11
3 3
Output
1
-1
6
21
6
62

Show the explanation of Sample 1 (click to expand)
Initially, the graph has $N$ vertices and $0$ edges. The variable is initialized to $X = 1$.
  • 1 0 1: The 1st query connects vertex $0$ and vertex $X = 1$ with an edge of weight $1$.
  • 2 0 1: The 2nd query outputs the distance ${\rm dist}(0, 1) = 1$ between vertex $0$ and vertex $1$. We add $1$ to the variable $X$ and take the remainder modulo $5$. The variable $X$ becomes $2$.
  • 2 0 2: In the 3rd query, vertex $0$ and vertex $2$ are not connected, so output $-1$.
  • 1 0 2: The 4th query connects vertex $0$ and vertex $X = 2$ with an edge of weight $2$.
  • 3 1: The 5th query asks for the sum of the distances over the pairs of vertices in the connected component containing vertex $1$.
    Since ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(1,2) = 3$, output their sum, $6$.
  • 4 4: The 6th query adds $4$ to the variable $X$ and takes the remainder modulo $5$. The variable $X$ becomes $1$.
  • 1 3 5: The 7th query connects vertex $3$ and vertex $X = 1$ with an edge of weight $5$.
  • 3 3: The 8th query asks for the sum of the distances over the pairs of vertices in the connected component containing vertex $3$.
    Since ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(0,3) = 4, {\rm dist}(1,2) = 3, {\rm dist}(1,3) = 5, {\rm dist}(2, 3) = 6$, output their sum, $21$.
  • 2 3 2: The 9th query outputs the distance ${\rm dist}(3, 2) = 6$ between vertex $3$ and vertex $2$. We add $6$ to the variable $X$ and take the remainder modulo $5$. The variable $X$ becomes $2$.
  • 1 4 11: The 10th query connects vertex $4$ and vertex $X = 2$ with an edge of weight $11$.
  • 3 3: The 11th query asks for the sum of the distances over the pairs of vertices in the connected component containing vertex $3$.
    Since ${\rm dist}(0,1) = 1, {\rm dist}(0,2) = 2, {\rm dist}(0,3) = 4, {\rm dist}(0,4) = 9,{\rm dist}(1,2) = 3, {\rm dist}(1,3) = 5, {\rm dist}(1,4) = 8, {\rm dist}(2, 3) = 6,$
    ${\rm dist}(2, 4) = 11, {\rm dist}(3, 4) = 13$, output their sum, $62$.

Sample 2
Input
7 5 15
2 0 5
1 1 542099847
1 0 126014135
2 6 1
1 3 606571677
1 4 630122460
3 2
2 5 3
2 6 6
1 2 660183552
3 3
2 1 3
2 5 1
2 5 2
3 1
Output
-1
-1
0
606571677
0
995222351
73942298
542099847
58594973
995222351

Sample 3
Input
8 3 10
2 6 2
1 1 789992496
1 4 345094264
1 2 654214606
1 5 184875134
3 1
1 7 378850180
1 0 389600407
3 0
2 2 3
Output
-1
900591855
327463395
654214606

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。