問題一覧 > 通常問題

No.2295 Union Path Query (Medium)

レベル : / AI推定難易度 : 1825 / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 24
作問者 : t98slider / テスター : akakimidori
お気に入りにしたユーザー ProblemId : 9156 / 自分の提出
問題文最終更新日: 2023-05-11 02:56:41
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 $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), 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} \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もしくは右上の雲マークをクリックしてアカウントを作成してください。