Entries

スポンサーサイト (この記事を編集する[管理者用])

上記の広告は1ヶ月以上更新のないブログに表示されています。
新しい記事を書く事で広告が消せます。

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1996-7e85bca5
この記事にトラックバックする(FC2ブログユーザー)

UVa 11987 - Almost Union-Find (この記事を編集する[管理者用])

Source

Rujia Liu's Present 3: A datastructure contest celebrating the 100th anniversary of Tsinghua University (2011-04-23) (blog)
UVa 11987

問題概要

1~N (100000以下) までの数字がある.
最初は,それぞれ1つの数字のみからなる集合に属している.(最初,集合はN個ある)
以下の形式のクエリが100000個以下与えられるので,それをこなす問題.
 1. 2つの数字pとqが属している集合を合併させる (pとqがすでに同じ集合に属すなら無視する)
 2. 数字pを数字qが属している集合に移動させる (pとqがすでに同じ集合に属すなら無視する)
 3. 数字pが属す集合の,要素の数,要素の数字の和を求める.

解法

基本的にはUnionFindのまま.
親だけを覚えておくのではなく,子供も全部覚えておいて,移動させたときに繋ぎ直すと通った.

コメント

コメントの投稿

コメントの投稿
管理者にだけ表示を許可する

トラックバック

トラックバック URL
http://rsujskf.blog32.fc2.com/tb.php/1996-7e85bca5
この記事にトラックバックする(FC2ブログユーザー)

Appendix

Recent Articles

ブログ内検索

Ads


(プライバシーポリシー)
上記広告は1ヶ月以上更新のないブログに表示されています。新しい記事を書くことで広告を消せます。