No.2294 Union Path Query (Easy)
タグ : / 解いたユーザー数 27
作問者 :
akakimidori
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), output0.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もしくは右上の雲マークをクリックしてアカウントを作成してください。