Entries

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

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

コメント

コメントの投稿

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

トラックバック

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

UVa 11981 - Corrupted Friendship (この記事を編集する[管理者用])

Source

A Contest dedicated to Renat Mullakhanov (rem) (2011-04-16) (blog)
UVa 11981

問題概要

N個 (10^5以下) の招待状がある.
招待状を受け取った人は,自分用に1個確保し,自分の友達1人選んで残りの招待状をすべて渡す.
もう友達がいないなら,自分を招待してくれた人に残りの招待状をすべて返す.
返された場合も,まだ招待していない友達を1人選んで招待状をすべて渡す.
こうやって,最終的にN人の人が招待状を1枚ずつ持っている状態になった.
招待が成立した数と,招待された人の中で,確実に友達同士ではない組の数を求める問題.

解法

とりあえず,招待が成立した数はN-1でいい.
まず木を作る.
後は,それぞれ,あるノードの,子供Aの木のノード数,子供Bの木のノード数,…,を調べて,Aの木のノード数*Bの木のノード数などを足していく.
愚直にやると,子供が多いとTLEなので,子供の木Aと,それ以外の子供の木のノード数の和をかけて足していく.

コメント

コメントの投稿

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

トラックバック

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

Appendix

Recent Articles

ブログ内検索

Ads


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