103724: [Atcoder]ABC372 E - K-th Largest Connected Components
Memory Limit:256 MB
Time Limit:2 S
Judge Style:Text Compare
Creator:
Submit:11
Solved:0
Description
Score : $475$ points
Problem Statement
There is an undirected graph with $N$ vertices and $0$ edges. The vertices are numbered $1$ to $N$.
You are given $Q$ queries to process in order. Each query is of one of the following two types:
- Type $1$: Given in the format
1 u v
. Add an edge between vertices $u$ and $v$. - Type $2$: Given in the format
2 v k
. Print the $k$-th largest vertex number among the vertices connected to vertex $v$. If there are fewer than $k$ vertices connected to $v$, print-1
.
Constraints
- $1 \leq N, Q \leq 2 \times 10^5$
- In a Type $1$ query, $1 \leq u < v \leq N$.
- In a Type $2$ query, $1 \leq v \leq N$, $1 \leq k \leq 10$.
- All input values are integers.
Input
The input is given from Standard Input in the following format:
$N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$
Here, $\mathrm{query}_i$ is the $i$-th query and is given in one of the following formats:
$1$ $u$ $v$
$2$ $v$ $k$
Output
Let $q$ be the number of Type $2$ queries. Print $q$ lines. The $i$-th line should contain the answer to the $i$-th Type $2$ query.
Sample Input 1
4 10 1 1 2 2 1 1 2 1 2 2 1 3 1 1 3 1 2 3 1 3 4 2 1 1 2 1 3 2 1 5
Sample Output 1
2 1 -1 4 2 -1
- In the first query, an edge is added between vertices $1$ and $2$.
- In the second query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $1$-st largest vertex number is $2$, which should be printed.
- In the third query, two vertices are connected to vertex $1$: $1$ and $2$. Among them, the $2$-nd largest vertex number is $1$, which should be printed.
- In the fourth query, two vertices are connected to vertex $1$: $1$ and $2$, which is fewer than $3$, so print
-1
. - In the fifth query, an edge is added between vertices $1$ and $3$.
- In the sixth query, an edge is added between vertices $2$ and $3$.
- In the seventh query, an edge is added between vertices $3$ and $4$.
- In the eighth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $1$-st largest vertex number is $4$, which should be printed.
- In the eighth query, four vertices are connected to vertex $1$: $1,2,3,4$. Among them, the $3$-rd largest vertex number is $2$, which should be printed.
- In the tenth query, four vertices are connected to vertex $1$: $1,2,3,4$, which is fewer than $5$, so print
-1
.
Sample Input 2
6 20 1 3 4 1 3 5 2 1 1 2 3 1 1 1 5 2 6 9 2 1 3 2 6 1 1 4 6 2 2 1 2 6 2 2 4 7 1 1 4 2 6 2 2 3 4 1 2 5 2 4 1 1 1 6 2 3 3 2 1 3
Sample Output 2
1 5 -1 3 6 2 5 -1 5 3 6 4 4
Output
得分:475分
问题陈述
有一个有N个顶点和0条边的无向图。顶点编号为1到N。
你需要按顺序处理Q个查询。每个查询都是以下两种类型之一:
- 类型1:格式为
1 u v
。在顶点u和v之间添加一条边。 - 类型2:格式为
2 v k
。打印与顶点v相连的顶点中第k大的顶点编号。如果与v相连的顶点少于k个,打印-1
。
约束条件
- $1 \leq N, Q \leq 2 \times 10^5$
- 在类型1的查询中,$1 \leq u < v \leq N$。
- 在类型2的查询中,$1 \leq v \leq N$,$1 \leq k \leq 10$。
- 所有输入值都是整数。
输入
输入从标准输入以以下格式给出:
$N$ $Q$ $\mathrm{query}_1$ $\mathrm{query}_2$ $\vdots$ $\mathrm{query}_Q$
这里,$\mathrm{query}_i$是第i个查询,并且以以下格式之一给出:
$1$ $u$ $v$
$2$ $v$ $k$
输出
设$q$为类型2查询的数量。打印$q$行。 第$i$行应包含对第$i$个类型2查询的答案。
示例输入1
4 10 1 1 2 2 1 1 2 1 2 2 1 3 1 1 3 1 2 3 1 3 4 2 1 1 2 1 3 2 1 5
示例输出1
2 1 -1 4 2 -1
- 在第一个查询中,在顶点1和2之间添加了一条边。
- 在第二个查询中,与顶点1相连的两个顶点是:1和2。其中,第1大的顶点编号是2,应该被打印。
- 在第三个查询中,与顶点1相连的两个顶点是:1和2。其中,第2大的顶点编号是1,应该被打印。
- 在第四个查询中,与顶点1相连的两个顶点是:1和2,少于3个,所以打印
-1
。 - 在第五个查询中,在顶点1和3之间添加了一条边。
- 在第六个查询中,在顶点2和3之间添加了一条边。
- 在第七个查询中,在顶点3和4之间添加了一条边。
- 在第八个查询中,与顶点1相连的四个顶点是:1,2,3,4。其中,第1大的顶点编号是4,应该被打印。
- 在第九个查询中,与顶点1相连的四个顶点是:1,2,3,4。其中,第3大的顶点编号是2,应该被打印。
- 在第十个查询中,与顶点1相连的四个顶点是:1,2,3,4,少于5个,所以打印
-1
。
示例输入2
6 20 1 3 4 1 3 5 2 1 1 2 3 1 1 1 5 2 6 9 2 1 3 2 6 1 1 4 6 2