torus711 のアレ

主に競技プログラミングの問題について書きます.PC 以外だと数式が表示されないかもしれないです

素集合データ構造

AtCoder Beginner Contest 183, F : Confluence

問題文 https://atcoder.jp/contests/abc183/tasks/abc183_f 問題概要 $N$ 人の人がいて,人 $i$ はクラス $C_i$ に属している.以下の 2 種のクエリを処理せよ. クエリ 1 : 人 $a, b$ が含まれる集団が合流する クエリ 2 : 人 $x$ が属している集団で,ク…

AtCoder Regular Contest 107, C : Shuffle Permutation

問題文 https://atcoder.jp/contests/arc107/tasks/arc107_c 問題概要 $N \times N$ 行列 $a$ と整数 $K$ が与えられる.$a$ の要素は $1$ ~ $N^2$ の整数をちょうど一つずつ含む.ここで,次の 2 種類の操作を好きな順序で好きな回数行うことができる. 任…

AtCoder Regular Contest 106, B : Values

問題文 https://atcoder.jp/contests/arc106/tasks/arc106_b 問題概要 $N$ 頂点 $M $ 辺からなる単純無向グラフ(連結とは限らない)が与えられる.はじめ,各頂点 $i$ には整数 $a_i$ が書かれている.ここで,次の操作を任意回行うことができる. 辺 $\{ u…

ACL Beginner Contest, C : Connect Cities

問題文 https://atcoder.jp/contests/abl/tasks/abl_c 問題概要 $N$ 個の街と $M $ 本の道路がある.$i$ 番目の道路は街 $A_i$ と $B_i$ を双方向に繋いでいる. ここに,新たに(双方向の)道路を作る操作を任意の回数行うことができる.任意の街から任意の…

AtCoder Beginner Contest 177, D : Friends

問題文 https://atcoder.jp/contests/abc177/tasks/abc177_d 問題概要 $N$ 人の人がいて,「人 $A_i$ と人 $B_i$ が友達である」という情報が $M $ 個与えられる.ここで,友達関係は transitive である(その情報が与えられるとは限らない*1). 人々をいく…