No.2295 Union Path Query (Medium)
タグ : / 解いたユーザー数 24
作問者 :
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 $0$ to $N-1$ .
The variable $X$ is initially set to $ X_{0} $.
The distance ${\rm dist} (u, v) $ between two vertices $u$, $v$ in the graph $G$ is defined as follows, that is, as the minimum, over all paths from one of the two vertices to the other, of the maximum weight among all edges in the path.
$$
{\rm dist} (u, v) = 頂点\ u\ から頂点\ v\ へのパスに含まれる辺すべての重みの最大値の最小値
$$
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 $w$ is non-decreasing in input order.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$ (vertex $v$ alone), 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} \leq 10^{9}$
・$w_{i} \leq w_{j}$ holds when $i < j$. - All input values are integers.
Output
Letting $K$ be the total number of type 2 and type 3 queries given, print the answer to each query on its own line, with the $i\ (1 \leq i \leq K)$-th answer on the corresponding line. Print a newline at the end.
Sample
Sample 1
Input
5 1 10 1 0 1 2 0 1 1 1 2 2 0 2 3 1 2 4 1 1 1 4 4 1 1 4 4 3 1
Output
1 2 5 -1 17
View the explanation of Sample 1 (click to expand)

Initially, the graph has $N$ vertices and $0$ edges, and the variable is initialized to $X = 1$.
1 0 1: In the 1st query, connect vertex $0$ and vertex $X = 1$ with an edge of weight $1$. (b)2 0 1: In the 2nd query, output ${\rm dist}(0, 1) = 1$. The variable becomes $X = 1 + 1 = 2$. (c)1 1 2: In the 3rd query, connect vertex $1$ and vertex $X = 2$ with an edge of weight $2$. (d)2 0 2: In the 4th query, output ${\rm dist}(0, 2) = 2$. The variable becomes $X = 2 + 2 = 4$. (e)3 1: In the 5th query, output the sum of the distances over pairs of vertices belonging to the same connected component as vertex $1$. (e)
Since ${\rm dist}(0, 1) = 1$, ${\rm dist}(0, 2) = 2$, ${\rm dist}(1, 2) = 2$, output their sum $5$.2 4 1: In the 6th query, ${\rm dist}(4, 1)$ is requested, but the vertices are not connected, so output $-1$. (e)1 1 4: In the 7th query, connect vertex $1$ and vertex $X = 4$ with an edge of weight $4$. (f)4 1: In the 8th query, add $1$ to the variable $X$ and take the remainder modulo $N$. This gives $ X = (4 + 1) \bmod 5 = 0$. (g)1 4 4: In the 9th query, connect vertex $4$ and vertex $X = 0$ with an edge of weight $4$. (h)3 1: In the 10th query, output the sum of the distances over pairs of vertices belonging to the same connected component as vertex $1$. (h)
Since ${\rm dist}(0, 1) = 1$, ${\rm dist}(0, 2) = 2$, ${\rm dist}(0, 4) = 4$, ${\rm dist}(1, 2) = 2$, ${\rm dist}(1, 4) = 4$, ${\rm dist}(2, 4) = 4$, output $17$.
Sample 2
Input
10 2 12 1 0 14 2 0 2 1 2 22 1 1 28 1 7 94 2 4 6 3 8 1 5 126 1 3 212 1 6 223 1 9 245 3 6
Output
14 -1 0 4135
Sample 3
Input
4 2 11 1 3 91 1 0 111 2 1 0 3 2 2 0 1 1 1 210 1 2 230 3 1 2 3 3 2 0 3 2 1 2
Output
-1 313 -1 943 0 111 210
提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。